۱ مقدمه. ۴

‏۲ انواع روش های تشخیص نرم افزارهای مضر/بداندیش…. ۵

‏۳ رویکرد پیشنهادی در شناسایی و تشخیص نوع نرم افزارهای مضر/بداندیش…. ۵

۳٫۱ تحلیل رفتار نرم افزارهای بداندیش/ مضر و استخراج رفتار آنها ۶

۳٫۲ بازنمایی رفتار کدهای بداندیش/ مضر. ۶

۳٫۳ استخراج خصوصیات مهمتر. ۸

۳٫۳ شناسایی نرم افزارهای مضر/ملور ها با استفاده از روش های طبقه بندی و تحلیل رگرسیون.. ۱۱

۳٫۳٫۱ ابزار WEKA… 11

۳٫۳٫۲ پیش پردازش – کاهش ابعاد داده ۱۳

۳٫۳٫۳ ساختن و آموزش مدل (طبقه بند: Classifier ) 17

۳٫۳٫۴ روش انجام کار و ارایه و بررسی نتایج بنابر روش های مختلف داده کاوی.. ۱۸

۳٫۳٫۵ بررسی خروجی الگوریتم های طبقه بندی در Weka. 24

۴ پیوست الف روشهای کاهش ویژگی.. ۲۷

۴٫۱ روشهای مبتنی بر استخراج ویژگی.. ۲۷

۴٫۲ روشهای مبتنی بر انتخاب ویژگی.. ۳۱

۵ پیوست ب : روشهای داده کاوی و شناسایی الگو و پیشبینی.. ۴۳

۵٫۱ دسته بندی/ طبقه بندی ۴۳

۵٫۲ رگرسیون.. ۴۵

۵٫۳ رگرسیون منطقی.. ۴۵

۵٫۴ پیش بینی سری های زمانی.. ۴۶

۵٫۵ تفاوت دسته بندی و رگرسیون.. ۴۶

۵٫۶ خوشه‌بندی.. ۴۸

۵٫۷ الگوریتم های دسته بندی : درخت تصمیم گیری و K-NN… 50

۶ پیوست ج: استخراج خصوصیات نرمافزارهای مضر/ملور ها به منظور بازنمایی رفتار آنها- توضیحات تکمیلی.. ۵۲

فهرست منابع و مراجع. ۵۴
۱ مقدمه

گرایش تشخیص نرم­افزارهای مضر یکی ازموضوعات  فعال و بحث برانگیز درحوزه­های امنیت رایانه است و در سالهای اخیر شاهد افزایش عجیبی در تعداده نرم­افزارهای مضر [۱] گزارش شده فروشندگان نرم­افزارهای ضد ویروس بوده­ایم . در این گزارش سعی بر این است که روشی جدید برای تشخیص نرم­افزارهای مضر – که در این گزارش مطابق اصطلاح متداول در اکثر قسمتها ملور(malware) نامیده می شود – از طریق بررسی رفتار آنها ارایه نماییم . ملور ها شامل تمام انواع نرم افزارها یا کدهای کامپیوتری هستند که می توانند به سیستم شما آسیب رسانده یا تغییر ناخواسته ای در آن ایجاد کنند، ملورها شامل ویروس ها، adware ها، spyware ها و Trojan ها هستند. این ارایه روشی موثر را  با استفاده ازتکنیک­های مهندسی معکوس به همراه داده کاوی و تشخیص الگو برای شناسایی ملورها و تشخیص نوع آنها معرفی می­نماید. در این روش با استفاده از ابزارهای تحلیلگر پویا[۲] گزارش رفتار برنامه ها در طول  اجرا تهیه شده و پس از ان با مشاهده و بررسی انواع گسترده ای از فایل های مضر خصوصیات مهم و موثر این فایل ها (مالورها) مشخص شد، لازم به ذکر است که مقدار زیادی از اطلاعاتی که در گزارش فایل برنامه مضر وجود دارد ممکن است در یک فایل سالم نیز دیده شود، لذا علاوه بر بررسی فایل های مضر، گزارش و عملکرد این فایل ها با فایل های سالم مقایسه شد تا همزمان که خصوصیات مشترک فایل های مضر استخراج می شود، این خصوصیات انتخاب شده نشانگر بیشترین تفاوت با فایل های سالم باشند به این معنی که یا خود خصوصیت در رفتار برنامه های سالم وجو نداشته باشد و یا مقدار آن صفر باشد و یا رنج مقادیری که در برنامه های سالم و مضر به آن تخصیص می یابد متفاوت باشد تا بتوان با استفاده از آنها به درستی الگوی رفتاری فایل های مضر را شناسایی کرده و فایل های مضر جدید را تشخیص و طبقه بندی نمود. پس از انتخاب این خصوصیات با استفاده از استانداردها و قوانینی که برای این منظور درنظر گرفتیم مقدار عددی این خصوصیات از متن گزارشات بیرون کشیده شد. سپس با انتخاب الگوریتمهای مناسب انتخاب و یا کاهش [۳]ویژگی (خصوصیت)، خصوصیاتی که بیشترین میزان تاثیر را در استخراج و تشخیص الگوی[۴] عملکرد این فایلها داشته بیرون کشیده شد که این کار منجر به افزایش سرعت و دقت طبقه بند در مرحله بعد شد. در نهایت با استفاده از طبقه بندهای مناسب نوع ملورها تشخیص داده شد. این رویکرد به یک روش یا ابزار خاص محدود نیست و می­توان آن را به اشکال مناسب  به کار برد .

 
‏۲ انواع روش های تشخیص نرم افزارهای مضر/بداندیش

در مباحث مهندسی معکوس برای تحلیل برنامه ها از دو روش ایستا و پویا استفاده می شود، لذا برای شناسایی ملوارها می توان از تحلیل ملوار با هر کدام از این روش ها یا ترکیب آن دو کمک گرفت. این دو روش هر کدام در جای خود مزایایی و معایبی دارند.با تحلیل استاتیک یک ملور را بدون اجرا کردن آنالیز می­کنند ، برای تشخیص ملور-مانند ویروس ها- به کمک تحلیل استاتیک ، کد برنامه را که به شکل باینری است گرفته و با تطابق دادن الگوی آن با پایگاهی از الگولهایی که از قبل تهیه شده است نسبت به تشخیص اقدام می­کنند که این روش اساس کار ضدویروسهای موجود است . برای انجام این کار از الگوریتم­های بسیاری استفاده می­شود از مزایای آن می­توان به اجرا نکردن کد آلوده و سرعت آن اشاره نمود ومعایب آن عدم کارایی در تشخیص کدهای آلوده­ و پیچیده­ای است که در ابتدا سالم به نظر می رسند ولی در هنگام اجرا تغییر ماهیت داده (خود را تغییر داده) و به کد مضر تبدیل می شوند و یا کدهایی که به صورت رمز درآمده اند و بررسی متن واقعی کد این برنامه ها مقدور نمی باشد در نتیجه بررسی استاتیک کد این برنامه ها در تشخیص رفتار مضر این برنامه ها بی فایده می باشد، در حالی که در تحلیل پویا رفتار خطرناک و مضر این برنامه ها تشخیص داده می شود و این مسئله برتری بررسی پویا نسبت به ایستا را روشن می کند. تحلیل استاتیک عموما به کمک یک دیباگر یا دیس­اسمبلر انجام می شود و تحلیل پویا به کمک یک دیباگر انجام میگردد . در تحلیل پویا (رفتاری) ما فایلی را که بررسی میکنیم مانند یک جعبه سیاه در نظر میگیریم و از روی رفتار ان به نتیجه میرسیم که چه منظور و هدفی دارد و کد باینری مورد بررسی قرار نمی گیرد ولی همانطور که مشخص می باشد باید برنامه ملور را اجرا نمود که این مسئله برای سیستم خطرناک است، البته می توان از روشها و ابزارهایی مانند ماشین مجازی[۵] برای ایجاد محیط امن استفاده نمود.
azsoftir.com
09367292276
09367292276
azsoftir@gmail.com
azsoftir.com
09367292276
09367292276
azsoftir@gmail.com
azsoftir.com
 
‏۳ رویکرد پیشنهادی در شناسایی و تشخیص نوع[۶] نرم افزارهای مضر/بداندیش
۳٫۱ تحلیل رفتار نرم افزارهای بداندیش/ مضر و استخراج رفتار آنها

ابزارهای زیادی برای بررسی کردن رفتار به صورت پویا وجود دارد از جمله تحلیاگرهای پویا و ابزارهای monitoring رفتار کد (process monitor ها)، که ما در این قسمت از دو تحلیل گر Anubis و CWSandbox استفاده کردیم به دلیل اینکه این دو ابزار تمامی خصوصیات رفتاری لازم را در گزارشات خود مشخص می کنند. این دو ابزار که به صورت ان­لاین کار بررسی فایل را انجام می دهند گزارش خود را در انتهای بررسی هر فایل به صورت انواع فایل هایhtml, xml, rtf ,… در اختیار کاربران قرار میدهند، در این پروژه برای استفاده در مراحل بعدی نوع xml انتخاب شد.

ابزارهای on line فایلهایی را که قرار است بررسی کننند در یک محیط کنترل شده اجرا میکنند به همین جهت پیشنهاد میگردد که خودتان نسبت به انجام این کار در محیط ویندوز خود اقدام نکنید و در استفاده از ابرارهای بررسی رفتار با احتیاط استفاده کنید زیرا یک سری از این ابزارها فایل مورد نظر را بر روی سیستم جاری دیباگ می کنند و منجر به ویروسی شدن سیستم شما خواهند شد. این کار میتواند برای دقت بیشتر با طبقه بندی یا خوشه بندی نیز همراه گردد. در خوشه بندی الگوی گونه­های جدید که از قبل نوع یا label آنها مشخص نشده را شناسایی کرده و فایل های مشابه در یک خوشه قرار داده می شوند، سپس می توان با توجه به نظر فرد خبره برای آنها نام یا نوع مشخص کرد، این روش در واقع نوعی پیش پردازش محسوب می شود و فایل هایی که شبیه هم اند در خوشه های مشابهی قرار می گیرند. بدین منظور لازم است تا معیاری برای بیان همسایگی میان نقاط جهت تشکیل خوشه ها تعریف گردد. در حالی که در طبقه بندی الگوی گونه­های شناخته شده موجود (که از قبل نوع آنها مشخص شده) را بنا بر داده های موجود استخراج کرده و سپس فایل های ناشناخته جدید را بنا بر مشابهت با الگوهای موجود در کلاس مربوطه طبقه بندی کرده و نوع آن را تشخیص می دهیم، هر طبقه که با برچسبهایی مشخص شده دارای ویژگیهای خاصی می باشد، با توجه به ویژگیها و قانونمندی هایی که برای هر نوع از پیش قائل شده ایم و یا از داده های موجود استخراج شده، تعلق فایل مورد نظر به هریک از طبقه ها مشخص می شود. در این پروژه از آنجا که نوع مالور های مورد بررسی از پیش مشخص می باشد ما لز روش طبقه بندی استفاده می کنیم.
۳٫۲ بازنمایی[۷] رفتار کدهای بداندیش/ مضر

پس از دریافت گزارش رفتار مالوار از طریق ابزارهای نامبرده به صورت متنی یا xml ، این موارد که برای آنالیز انسانی مناسب است بایستی به یک شکلی تغیر یابد که قابلیت تحلیل خودکار توسط سیستم را داشته باشد،. این گزارش xml بسیار غنی است و موارد بسیاری از خصوصیات رفتاری و عملکرد فایل در ان موجود است که از طریق نگاه کردن به ان میتوان یک دید کلی از رفتار، عملکرد و ردپای ان کد/ برنامه مشخص را بدست آورد . به دلیل ساختار داده­ای گزارش xml و برتری ان نسبت به متنی ما این نوع گزارش را برای بررسی در نظر گرفتیم .
azsoftir.com
09367292276
09367292276
azsoftir@gmail.com
azsoftir.com
09367292276
09367292276
azsoftir@gmail.com
azsoftir.com
فایل xml که در زیر شمایی از آن را می­بینید شامل عملکردهای اصلی برنامه است (کلیه فعالیت هایی که یک برنامه در هنگام اجرا انجام داده است):

 

در ابتدا اطلاعات مربوط به خود گزارش مشاهده می شود، مانند زمان گزارش، فایل مورد بررسی، مسیر آن و …، یک سری از این اطلاعات خاص خود CWSandbox می باشد که این گزارش را تهیه کرده مانند ورژن آن (اولین خصوصیت)، اکثر گزارشات شامل ۳ تگ اصلی می باشد، شامل calltree, processes, running processes ، به صورت تودرتو هر تگ اصلی شامل تگ های دیگر می باشد، در تگهای اصلی اولین تگی که بایستی توضیح دهیم تگ CallTree است که در آن فرایندهایی که توسط مالوار ایجاد شده­اند را می­توانید به صورت کلی همراه با اطلاعات اصلی شان ببینید، به طور مثال در شکل بالا در مجموع شش فرایند در یک بار اجرای فایل اصلی ایجاد شده­اند، در صورتی که در هنگام اجرای یکی از این پروسه ها، پروسه های دیگری درون آن ایجاد شود به صورت سلسه مراتبی و تودرتو این پروسه ها در پروسه پدر نمایش داده می شوند، و همان ساختار قبلی رعایت می شود. هر کدام از این فرایندها به طور جداگانه در تگ Processes که در اینجا آبی رنگ نشان داده شده است به تفصیل همراه با تمامی خصوصیات رفتاری مانند اعمالی که در هر process انجام شده، ردپا و اثری که در قسمت های مختلف سیستم از خود به جا گذارده و تغییراتی که ایجاد می کند توضیح داده می­شود.

در تگ Processes بنا برتعداد فرایندها شاخه وجود دارد که هر کدام از فرایندهای اجرا شده می­توانند شامل بخش ها ی(تگ های) زیر باشند که در هر کدام مقدار یکی از خصوصیات رفتاری فایل مشخص می شود.

    dll_handling_section شامل اطلاعات مربوط به فراخوانی تعدادی از فایلهای کتابخانه­ای
    filesystem_section شامل اطلاعات مربوط به ایجاد ، جستجو، تغییر در فایلها
    registry_section شامل اطلاعات مربوط به تغییراتی که برنامه در رجیستری ایجاد کرده
    process_section شامل اطلاعات مربوط به فرایندها
    ایجاد Mutex
    virtual_memory_sectionشامل اطلاعات مربوط به دستکاری و تغییرات حافظه مجازی توسط برنامه
    ارسال پست الکترونیک
    ارتباط از طریق سوکتها
    …

تعداد این تگ ها برای یک پروسه ممکن است بسیار بیشتر از موارد ذکر شده در بالا باشد ، این ۸ مورد که از مهمترین موارد می باشند به عنوان نمونه انتخاب شده اند.

 
۳٫۳ استخراج خصوصیات مهمتر
azsoftir.com
09367292276
09367292276
azsoftir@gmail.com
azsoftir.com
09367292276
09367292276
azsoftir@gmail.com
azsoftir.com
پس از نگاه کلی به فایلهای گزارش، بررسی گزارش فایل های مضر و مقایسه اولیه آنها با گزارش فایل های سالم (در ادامه بررسی و مقایسه های دقیقتر انجام شد) یک سری خصوصیات که مهم تر به نظر می رسیدند انتخاب شدند، هر کدام از این خصوصیات نماینده یکی از تگ های گزارش می باشد، (ممکن است این تگ به صورت تودرتو در یک تگ دیگر وجود داشته باشد و نمایانگر خصوصیت رفتاری مهمی از برنامه موردنظر باشد). مقدار عددی هر کدام از پارامترهای انتخابی برای هر فایل (برنامه) مورد بررسی به صورتی که در ادامه توضیح داده می شود مشخص شد .

برای انجام این کار برنامه­ای به زبان ویژوال بیسیک نوشته شد که بتواند اطلات مورد نیاز را از میان حجم انبوه دادهای برگشتی از تحلیل رفتار مالوار به ما بدهد که بتوانیم در تحلیل خودکار توسط سیستم در قسمت های بعدی از آنها استفاده کنیم. این برنامه ابتدا خصوصیات مورد نظر را از میان سایر اطلاعات استخراج و سپس مقدار عددی مناسب را به آن تخصیص می دهد، به این ترتیب به مرور و به صورت مرحله به مرحله برای هر ملور آرایه ای (vector ی) کامل می شود که هر خانه آن مقدار عددی مربوط به یک خصوصیت رفتاری ملور را داراست در این بخش با توجه به تجربیات قبل از نگاه به خصوصیات فایلها ابتدا تعداد load کردن تعدادی از فایلهای کتابخانه­ای[۸] را مورد ارجاع قرار گرفته بودند در نظر گرفتیم پس از تحلیل بر روی آنها متوجه شدیم که این پارامترها نمیتواند دقیق باشند چرا که قدرت تشخیص را در حدی پایینتر از ۲۰ درصد نگاه میداشت . پس با نگاهی دوباره به مالوارها متوجه شدیم که تمامی مالوارهایی که در یک دسته قرار میگیرند میزان فضای اشغالی آنها نزدیک به هم است پس میزان بزرگی فایل ها را به عنوان ضریبی در میزان تعداد مراتبی که در هر مالوار که بار [۹]شده بودند ضرب کردیم و برای هرکدام اعدادی مابین ۰ تا ۲ به دست آمد که این را میزانی برای تشخیص گذاشتیم :

Nqty=NewAttrib quantity=Dll calls * file weight

در این مرحله تحلیل بر روی خصوصیات انتخابی، کارایی را مابین ۵۰ تا ۶۰ درصد نشان میداد  که هنوز ناکافی به نظر میرسید . پس سعی بر این شد که خصوصیتی دیگر را نیز در نظر بگیریم که برای این مورد نیز برنامه نوشته شده خصوصیاتی دیگر از جمله تعداد بارهایی که یک فایل را باز میکند یا یک فایل را جستجو میکند و اینکه تعداد موتکس­هایی که ایجاد میگردد و همچنین تعداد باری که این مالوار فرایندهایی را ایجاد میکند به مجموعه خصوصیات ما اضافه شد . در ادامه ما به مرحله تشخیص موثرترین خصوصیات از میان ۹۰ خصوصیات انتخابی رسیدیم.حال برای آنالیز داده­ها بایستی آن را به یک شکل خاص غیر اسپارس برای افزایش سرعت و راحت برای تحلیل در نرم­افزار Weka تبدیل می­کردیم مجموع دادهای گردآوری شده از میان بیش از ۳۰۰۰۰ مالوار است که برای هرکدام یک بردار خصوصیات به شکل زیر ایجاد شد .

{(Attribnumber nqty)* , Malware type }

{۴۵ ۰٫۱۰۷, ۴۶ ۰٫۱۰۷, ۴۷ ۰٫۱۰۷, ۴۸ ۰٫۱۰۷, ۴۹ ۰٫۱۰۷, ۵۰ ۰٫۱۰۷, ۵۱ ۰٫۱۰۷, ۵۲ ۰٫۱۰۷, ۵۳ ۰٫۱۰۷, ۵۴ ۰٫۱۰۷, ۵۵ ۰٫۱۰۷, ۵۶ ۰٫۱۰۷, ۷۳ ۰٫۱۰۷, ۸۷ ۱, ۸۸ T24}

در این گزارش هر بخش با یک کاما از بخش دیگر که خصوصیاتی را بیان می­کند جدا می­شود . به طور مثال عبارت ۴۶ ۰٫۱۰۷ بیانگر این است که به خصوصیت شماره ۴۶ که اکنون پارامتر ۴۶ است مقدار عددی مقابل آن تخصیص پیدا کرده است. این عدد از حاصل ضرب تعداد بارهایی که تابع کتابخانه­ای شماره ۴۶ بار شده و استفاده گردیده است در میزان حجم فایل که عددی بر حسی مگابایت است به دست آمده است .

نمونه پارامترهای مهم انتخابی در زیر آورده شده است :
شماره پارامتر     نام پارامتر     شماره پارامتر     نام پارامتر
۱     version.dll     ۶۶     userenv.dll
۱۵     ws2help.dll     ۷۲     urlmon.dll
۴۳     Wininet.dll     ۸۵     Open_file
۴۶     Ntdll.dll     ۸۶     find_file
۴۷     kernel32.dll     ۸۷     delete_file
۶۴     shell32.dll     ۸۸     create_mutex
        ۸۹     process_call

 

به عنوان نمونه اطلاعات مرتبط با یک بخش خاص از فایل XML به شکل زیر :

<load_dll filename=”C:\WINDOWS\system32\ole32.dll” successful=”1” address=”$774B0000” end_address=”$775ED000” size=”1298432” quantity=”4” />

اینگونه استخراج می­گردد که مثلا فایل ole32.dll در چند جا و به چه تعدادی فراخوانی شده که در بالا می­بینید که تعداد ۴ است و برای هر DLL یا فایل سیستمی خاص این عملیات انجام می­گیرد و هر مقداری که بدست آمد در میزان حجم فایل بر حسب مگابایت مانند ۰٫۰۸۷۶ ضرب شده و مقدار جدید را تا ۳ رقم گرد می­کنیم و این اطلاعات را ذخیره می­کنیم . اما در موارد ۸۵ تا ۸۹ به دلیل اهمیت آنها ، مقادیر به صورت خام و همان تعدادی که فراخوانی شده در حاصل ذخیره می­گردد تا در نهایت یک سطر تشکیل گردد. برای جمع­آوری نمونه کد ملورهای های مختلف (source code یا object code یا کد اجرایی) برای آنالیز می­توانید باینری ملورها را از سایت اینترنتی http://vx.netlux.org/ دانلود نمایید و سپس در سایتهای http://anubis.iseclab.org و http://www.sunbeltsecurity.com/sandbox/default.aspx   نتایج تحلیل رفتاری را برای این باینریها مشاهده و دانلود کنید . همچنین از قبل یک سری مجموعه گزارش آماده از رفتار تعداد زیادی ملور که توسط همین شرکتها آماده شده است در سایت اینترنتی http://pi1.informatik.uni-mannheim.de/malheur قابل دریافت است که تعداد داده­های آن بالغ بر ۳۰۰۰۰ مالوار در انواع متفاوت است . برای دریافت فایلهای XML که به صورت فشرده قرار دارند به پایین صفحه لینک بالا مراجعه نمایید و از لیست فایلهای CWsandbox موارد مورد نیاز را دانلود نمایید. برای مشاهده لیست خصوصیات انتخاب شده توسط تحقیق ما به پیوست ج مراجعه کنید.

برای اطلاع بیشتر از data set (مجموعه نمونه های) استفاده شده به پیوست ج مراجعه کنید.
۳٫۳ شناسایی نرم افزارهای مضر/ملور ها با استفاده از روش های طبقه بندی و تحلیل رگرسیون
۳٫۳٫۱ ابزار WEKA

نرم­افزار WEKA یکی از ابزارهای معروف داده کاوی می باشد که الگوریتم های معروف زبادی را برای طبقه­بندی ، خوشه بندی ، استخراج قوانین انجمنی و .. به صورت آماده مهیای استفاده می­نماید. به این دلیل است که از weka می توان علاوه بر داده کاوی در کاربرد های تشخیص الگو نیز استفاده نمود، با استفاده از الگوریتم مناسب در weka می توان مدلی را برای استفاده در آینده ساخت. در پروژه فعلی این مدل یک classifier یا طبقه بند می باشد که برای روش classification یا طبقه بندی در این مدل می توان از الگوریتم های مختلفی استفاده نمود، مانند درخت های تصمیم گیری. با استفاده از مجموعه داده­های موجود و گردآوری شده از یک عملیات خاص (در این مثال تحلیل رفتاری ملور) می توان مدل مورد نظر را آموزش و در موارد جدید از آن استفاده نمود. نرم­ افزار WEKA در دانشگاه وایکاتو در نیوزیلند پیاده سازی شده است. قالب دریافت اطلاعات در این نرم­افزار ARFF است که به شکل زیر می­باشد .

@RELATION main                                             نام فایل

@ATTRIBUTE dll1   numeric                      خصوصیت

@ATTRIBUTE dll2   numeric                       خصوصیت

@ATTRIBUTE dll3   numeric                       خصوصیت

@ATTRIBUTE dll4   numeric                       خصوصیت

…………………….                                           خصوصیت

@ATTRIBUTE param85       numeric                خصوصیت
azsoftir.com
09367292276
09367292276
azsoftir@gmail.com
azsoftir.com
09367292276
09367292276
azsoftir@gmail.com
azsoftir.com
@ATTRIBUTE class {T0, T1, T2, …. }              جواب – خصوصیت

@DATA

۸٫۷۶۳,۴۳٫۸۱۶,۰,۴٫۳۸۱,۴٫۳۸۱,۰,۰,۸٫۷۶۳, … , T1

…………….

همانگونه که می­بینید در ابتدا نام فایل مشخص می­گردد سپس تعداد خصوصیات یا پیشگوها را با تعریف یک نام برای هر کدام و تعیین فرمت برای هر کدام مشخص می­کنیم . آن خصوصیتی که به عنوان جواب انتخاب می­گردد نیز تفاوتی با دیگر خصوصیات نداشته و هر کدام می­تواند با توجه به تحلیل و استنتاج به عنوان جواب در نظر گرفته شود. در ادامه به ازا هر فایل بررسی شده در یک خط (آرایه ، vector) مقدار عددی هر یک از این خصوصیات به ترتیب ذکر شده در بالا آورده می شود، و در نهایت مجموعه داده­های ما را شکل می دهد که از روی تحلیل رفتار مالوارها استخراج کرده­ایم. در نرم­افزار WEKA ما از یکی از محیط های گرافیکی آن به نام Explorer استفاده کردیم که خود شامل ۶ بخش است.

    Preprocess
    Classify
    Cluster
    Associate
    Select Attribute
    Visualize

در این مبحث قصد نداریم که به شکل کامل به نرم­افزار WEKA بپردازیم. درخلال کار قسمتهای مورد استفاده توضیح داده خواهد شد . جهت آشنایی با این نرم­افزار و الگوریتم­های مختلف آن به کتاب [۱۰] که در مراجع موجود است مراجعه نمایید.

 
۳٫۳٫۲ پیش پردازش – کاهش ابعاد داده

پیشرفتهای بوجود آمده در جمع آوری داده و قابلیتهای ذخیره سازی در طی دهه­های اخیر باعث شده در بسیاری از علوم با حجم بزرگی از اطلاعات روبرو شویم. محققان در زمینه­های مختلف مانند مهندسی، ستاره شناسی، زیست شناسی و اقتصاد هر روز با مشاهدات بیشتر و بیشتری روبرو می­شوند. در مقایسه با بسترهای داده­ای قدیمی و کوچکتر، بسترهای داده­ای امروزی چالشهای جدیدی در تحلیل داده­ها بوجود آورده­اند. روشهای آماری سنتی به دو دلیل امروزه کارائی خود را از دست داده­اند. علت اول افزایش تعداد مشاهدات (observations) است، و علت دوم که از اهمیت بالاتری برخوردار است افزایش تعداد متغیرهای مربوط به یک مشاهده می­باشد.

تعداد متغیرهایی که برای هر مشاهده باید اندازه گیری شود ابعاد داده نامیده می­شود. عبارت “متغیر” (variable) بیشتر در آمار استفاده می­شود در حالی که در علوم کامپیوتر و یادگیری ماشین بیشتر از عبارات “ویژگی” (feature) و یا “صفت” (attribute) و در تحلیهای آماری به عنوان پیشگوها استفاده می­گردد.

بسترهای داده­ای که دارای ابعاد زیادی هستند علیرغم فرصتهایی که به وجود می­آورند، چالشهای محاسباتی زیادی را ایجاد می­کنند. یکی از مشکلات داده­های با ابعاد زیاد اینست که در بیشتر مواقع تمام ویژگیهای داده­ها برای یافتن دانشی که در داده­ها نهفته است مهم و حیاتی نیستند. به همین دلیل در بسیاری از زمینه­ها کاهش ابعاد داده یکی از مباحث قابل توجه باقی مانده است.

روشهای کاهش ابعاد داده به دو دسته تقسیم می­شوند:

    روشهای مبتنی بر استخراج ویژگی: این روشها یک فضای چند بعدی را به یک فضای با ابعاد کمتر نگاشت می­کنند. در واقع با ترکیب مقادیر ویژگیهای موجود، تعداد کمتری ویژگی بوجود می­آورند بطوریکه این ویژگیها دارای تمام (یا بخش اعظمی از) اطلاعات موجود در ویژگیهای اولیه باشند. این روشها به دو دسته­ی خطی و غیر خطی تقسیم می­شوند.
    روشهای مبتنی بر انتخاب ویژگی: این روشها سعی می­کنند با انتخاب زیرمجموعه­ای از ویژگیهای اولیه، ابعاد داده­ها را کاهش دهند. در پاره­ای از اوقات تحلیلهای داده­ای نظیر طبقه­بندی برروی فضای کاسته شده نسبت به فضای اصلی بهتر عمل می­کند.

در تهیه این گزارش کمتر به اثباتهای ریاضی پرداخته شده و بیشتر به مفاهیم و کاربرد روشها توجه شده است. در بخش دوم از این گزارش، به مطالعه­ی روشهای مبتنی بر استخراج ویژگی پرداخته­ایم. در تهیه­ی مطالب این بخش سعی کرده­ایم با ارائه­ی مثالهای مناسب، خواننده را در درک بهتر مفاهیم مربوطه یاری رسانیم. در این بخش، چهار روش ارائه شده است که همگی از نوع خطی هستند. بدلیل حجم زیاد مطالب، مجالی برای پرداختن به روشهای دیگر خطی و روشهای غیر خطی باقی نماند. برای اطلاع از بعضی از روشهای استفاده شده به پیوست الف مراجعه نمایید.

برای انجام کارهای پیش پردازش ابتدا فایل با فرمت ARFF را از قسمت Open File بار می­کنیم سپس از بخش فیلتر ، مورد Unsupervised الگوریتم Normalize را انتخاب می­کنیم . اجرای این الگوریتم با زدن دکمه Apply باعث خواهد شد که داده­های ما بین ۰ تا ۱ قرار گیرند.

 

البته بایستی در انتخاب نوع الگوریتمها دقت نمود چرا که به شدت در نتیجه کار تاثیرگذار است. برای انجام قسمت دوم عمل پیش پردازش بایستی از قسمت Filter گزینه Supervised و Attribute و سپس Attribute Selection را انتخاب کرده و بعد از آن الگوریتم های موردنظر برای انتخاب و کاهش ویژگی ها را انتخاب می کنیم. کافیست با زدن کلید apply عملیات را اجرا نمایید تا نتیجه را که کاهش تعداد خصوصیات انتخابیست را ببینید، البته بعضی از روش های کاهش و انتخاب ویژگی با ترکیب ویژگی های موجود، ویژگی های جدیدی را تولید می کتتد . نتیجه اعمال بعضی از این روش مانند اینست که شما با توجه به میزان تاثیر هر یک از ویژگی ها به عنوان یک پیشگو ، پیشگو (ویژگی)های مهمتر را بایکی از الگوریتمها انتخاب و یا با توجه به میزان تاثیرشان ویژگی های جدید بوجود آورید.

azsoftir.com
09367292276
09367292276
azsoftir@gmail.com
azsoftir.com
09367292276
09367292276
azsoftir@gmail.com
azsoftir.com
برای نتیجه گیری انتخاب خصوصیات باید بگوییم که برای رسیدن به خروجی مناسب استفاده از الگوریتمهای فوق می­تواند بسیار مناسب باشد. در واقع عمل جداسازی یه دو صورت کنترل شده و نشده به صورت آماری به میزان قابل توجهی در دسته بندی خروجی و اعمال درختهای تصمیم گیری می­تواند موثر واقع شود. این تاثیر در بعضی مواقع تا بالای ۲۰ % هم در خروجیهای ما خود را نشان داده است.

این اتفاق به این علت است که اگر ما منحنی رگرسیون را برای خروجی رسم نماییم تا میزان تاثیر پیشگوها (ویژگی) را ببینیم بعضی از موارد بسیار مضر و مخرب عمل می­کنند ، با این عملیات ما تاثیر این موردها را کاهش می­دهیم و دقت را بالا میبربم.

این الگوریتمها را ما در دسته الگوریتمهای فیلترینگ بررسی کردیم.

 
۳٫۳٫۳ ساختن و آموزش مدل (طبقه بند: Classifier )

الگوریتمهای طبقه بندی برای ایجاد مدل (سیستمی) برای تشخیص نوع ملور های موجود یا جدید در weka عموما به ۶ دسته تقسیم میگردند که هرکدام در داخل خود الگوریتمهای متعددی دارند :

 

    Bayes
    Functions
    Lazy
    Meta
    Misc
    Trees
    Rules
    Immune
    Neural

 
azsoftir.com
09367292276
09367292276
azsoftir@gmail.com
azsoftir.com
09367292276
09367292276
azsoftir@gmail.com
azsoftir.com
برای انتخاب، آموزش و استفاده ازمدل در آینده بایستی به مرحله بعد در نرم­افزار WEKA رفته یعنی بخش Classify ، و یکی از الگوریتمهای دسته­بندی[۱۱] (طبقه بندی) را مورد استفاده قرار دهیم.

 
۳٫۳٫۴ روش انجام کار و ارایه و بررسی نتایج بنابر روش های مختلف داده کاوی

از بخش Classify در WEKA الگوریتم مورد نظر را انتخاب کرده و سپس برای ساختن، آموزش و ارزیابی طبقه بند موردنظر روش cross validation را انتخاب کرده و تعدادfold ها را ۱۰ در نظر گرفتیم سپس بر روی دکمه شروع زده و منتظر نتیجه باقی می­مانیم.

 

مدلهای مورد استفاده در تحلیل که بهترین نتایج را به ما دادند عبارتند از ۲ مورد اول و مورد سوم جزو روش های تکاملی است که به علت مزایایی که دارد امروزه در تشخیص ملور ها مورد توجه زیادی قرار گرفته است، البته روش های طبقه بندی دیگری نیز در آزمایشات متفاوت مورد بررسی قرار گرفت و این روش ها برای ارائه به عنوان نمونه انتخاب شدند :

 

        Classification via Regression
        Decision Tree C4.5
        Immune System

در حالت اول ابتدا از الگوریتم طبقه­بندی از طریق رگرسیون استفاده کردیم، برای ارزیابی و تست مدل از روش cross-validation و تعداد ۱۰ fold استفاده شد. در ابن حالت برای طبقه­بندی ۲۳ نوع ملور مدل ما توانست با دقت ۹۸٫۴۰۳۱ % نوع ملور ها درست تشخیص دهد،

 

 

 

همانگونه که در شکل بالا می­بینید که حاصل نتایج طبقه­بندی از طریق رگرسیون است از کل ۳۱۳۱ نمونه گرداوری شده ، الگوریتم توانسته است که ۳۰۸۱ مورد را در دسته(کلاس)­های مربوطه به درستی قرار دهد. این روش موارد را در یکی از شاخه های درختی مشابه درخت تصمیم­گیری قرار داده و سپس برای هر مورد یک معادله رگرسیون ایجاد می­کند که این معادلات رگرسیونی بر حسب مقادیر و ضرایب پیشگوها که در این جا feature های هر نمونه هستند تغییر می­کند و میزان تاثیر آنها درحالات مختلف در کلاس خروجی متفاوت است. در شکل زیر می­توانید ببینید که به صورت نمونه دسته­بندی و ضرایب برای هر معادله در یک مثال به چه شکلی است . در این روش برای استفاده از هر معادله در واقع قوانین و شرایطی برای مقادیر feature ها مشخص می شود، که در صورت دارا بودن آن شرایط از معادله ای که در انتهای شاخه برای بدست آوردن مقدار کلاس مشخص شده استفاده می شود. در این روش feature های انتخاب شده نقش پیشگو ها را در معادلات رگرسیونی بازی می کنند.

 

 

به عنوان نمونه در شکل بالا ، این گونه گفته می­شود که اگر پارامتر ۸۹ کوچکتر مساوی با ۰٫۰۰۲ بود و Dll47 مقدارش کوچکتر مساوی با صفر بود آنگاه معادله رگرسیونی LM1 را در نظر بگیر و به این ترتیب تمامی معادلات مشخص می­گردند. علی رقم مشابهت این روش با درخت های تصمیم گیری جهت این دو روش کمی متفاوت می باشند.

درحالت دوم از روش درخت های تصمیم گیری و الگوریتم C4.5 که از درخت های تصمیم محبوب می باشد نیز بر روی این داده ها استفاده شد و در همین حالت cross-validation با ۱۰ fold جواب مشابه ای بدست آمد که   ۹۸٫۷۲۲۵ % می باشد.

تفاوت روش طبقه بندی از طریق رگرسیون با درخت های تصمیم گیری در این می باشد که در روش اول شما در انتهای هر شاخه یک مدل رگرسیون (معادلع) خواهید داشت (که برای هر کلاس متفاوت می باشد) که از طریق آن مقدار کلاس محاسبه خواهد شد ولی در روش درخت های تصمیم گیری در انتهای هر شاخه مستقیما مقدار خود کلاس مشخص خواهد شد و اگر نمونه ای برحسب شرایط به انتهای یک شاخه برسد در آنجا مقدار کلاسی که به آن متعلق می باشد به طور دقیق ذکر شده است. البته بعد از آموزش سیستم (مدل) شاخه های درخت و مقادیر کلاس ها در انتهای هر شاخه مشخص می شود. برای درک این دو مدل به درخت تصمیم گیری در پیوست ب مراجعه کنید.

درحالت سوم الگوریتم AIRS (Artificial Immune Recognition System) را بر روی مجموعه داده­ها اجرا می­کنیم در مرحله اول این الگوریتم برای هر نوع یا کلاس یک تعداد نماینده بهینه از روی مجموعه داده های training بدست می آورد که تعداد آنها بسیار کمتر از داده های اصلی می باشد، سپس طبقه­بندی را توسط روش KNN با استفاده از نقاط نماینده هر کلاس انجام می­دهد. نقاط انتخاب شده همراه با داده های test ورودی الگوریتم KNN هستند و در KNN این نقاط برای تشخیص کلاس داده های تست استفاده می شود، در نتیجه این روش بسیار بهتر از KNN عمل می کند، در این روش قدرت تشخیص با همان روش cross-validation با ۱۰ fold دقت تشخیص درست ۸۱٫۹۸۶۶ % درصد است که از تعداد ۳۱۳۱ نمونه ۲۵۶۷ مورد را به شکل صحیح تشخیص می­دهد. نقطه برتری این روش با توجه به پایین بودن درصد طبقه­بندی آن ، قدرت تشخیص بالا برای نمونه ­های جدید است. در این پروژه از ورژن parallel الگوریتم AIRS استفاده شد که برای داده ای زیاد همراه با تعداد کلاس ها و feature های زیاد از سرعت بالایی برخوردار می باشد. این الگوریتم یک الگوریتم supervise الهام گرفته از سیستم ایمنی بدن می باشد که برای طبقه بندی از آن استفاده می شود.

 

از مدل های ایجاد شده در هر روش می توان برای شناسایی سایر ملور هایی که در data set آموزش (train) و تست ما موجود نبود استفاده کرد، البته این مدل ها قدرت خود را با روش cross-validation نشان داده اند، در همین روش نیز ابتدا data set به بخش های مساوی به تعداد fold ها تقسیم می شود، سپس به صورت متوالی بخشی از data set به صورت test و سایر بخش ها به عنوان train استفاده می شود تا تمام بخش ها به عنوان test برای مدل استفاده شود، پس در هر بار بعد از train سیستم با ملور های جدیدی مواجه می شود که قبلا آنها را ندیده و باید نوع آنها را تشخیص دهد.
azsoftir.com
09367292276
09367292276
azsoftir@gmail.com
azsoftir.com
09367292276
09367292276
azsoftir@gmail.com
azsoftir.com
البته مراحل آموزش و تست سیستم به صورت کاملا مجزا و با data setهای مجزا نیز انجام شد، برای این منظور data set اصلی به صورت random با درصد ۷۰-۳۰ جدا می شود. (ابتدا data set را randomize نمونه و سپس ۷۰% آن را برای train سیستم و ۳۰% آن را برای test سیستم جدا می کنیم). در این حالت ابتدا سیستم را با بخش جدا شده برای train آموزش می دهیم و سپس با استفاده از داده های تست دقت آن را در تشخیص ملورهای جدید ارزیابی می کنیم، نتایج بدست آمده (درصد میزان درستی تشخیص سیستم) برای داده های تست در هر روش در زیر آورده می شود، این نتایج نشان می دهد که مدل (سیستم) های بدست آمده برای تشخیص مالور های جدید قابل اعتماد خواهند بود.

 

Classification via Regression: 98.2979 %

Decision Tree (C4.5): 99.2553 %

Parallel AIRS: 85.7447 %

 
۳٫۳٫۵ بررسی خروجی الگوریتم های طبقه بندی در Weka

رای درک بهتر گزارش خروجی های weka بعد از اجرای هر الگوریتم (الگوریتم های طبقه بندی) توضیح مختصری در مورد قسمتهای مهم آن در ادامه آورده شده است، و نکاتی که هر مورد می توانند در بررسی قدرت و دقت مدل برای ما مشخص کنند بیان شده است.

مهمترین خروجی Correctly Classified Instances که تعداد و درصد نمونه هایی که درست شناسایی شده اند را مشخص می کند در واقع این عدد معیاری است برای ارزیابی میزان صحت و دقت عملکرد سیستم (مدل) بدست آمده، به طور مثال در این جا به ما نشان می دهد که این مدل تا چه حدی در تشخیص نوع برنامه های مضر/ ملور ها موفق بوده است، علاوه بر الگوریتم طبقه بندی انتخاب شده و پارامترهای الگوریتم که توسط ما به صورت دستی برای سیستم قبل از شروع آموزش انتخاب می شود، نمونه های جمع آوری شده و خصوصیات/ ویژگی های استخراج و انتخاب شده برای نمونه ها (در اینجا ملورها) نیز موثر می باشد، درصورتیکه نمونه ها با توزیع خوبی جمع آوری نشود به طوری که کل فضای آزمایش شما را پوشش ندهد سیستم نمی تواند همه کلاس ها را به خوبی شناسایی کند و یا بعد از آموزش در شناخت موارد جدید به خوبی عمل نخواهد کرد،درصورتیکه برای بردار ویژگی/ خصوصیت، مواردی انتخاب نشود که بردار ویژگی نماینده دقیقی از موارد مورد مطالعه باشد، به طور مثال در اینجا خصوصیات انتخاب شده به خوبی نشانگر رفتار ملورها نباشند، مسلما نتایج دلخواه بدست نخواهد آمد. البته نتایج ضعیف طبقه بندی ممکن آست ناشی از ضعف الگوریتم انتخاب شده و یا انتخاب اشتباه پارامترهای آن باشد، نتایج خوب بدست آمده در آزمایشات انجام شده در این پروژه بر روی طیف گستردهای از الگوریتم ها نشانگر آن است که ویژگی های خوبی از گزارشات رفتار ملورها استخراج شده است. نتایج طبقه بندی هم برای آموزش سیستم و هم برای تست آن در برابر داده های جدید می توان مشاهده نمود، که معمولا ابتدا سیستم با ۷۰% data set (مجوعه نمونه ها) آموزش داده می شود و سپس با ۳۰% نمونه های باقیمانده تست خواهد شد. در حالت تست داده ها را همراه جواب به سیستم می دهیم تا آموزش دیده و الگو های کلی هر کلاس را استخراج کرده و یاد بگیرد و پارامتر های خود را تنظیم کند و مدل ساخته شود، سپس مدل را با روی نمونه های جدید که جواب (کلاس) آن را نمی داند تست می کنیم، در هر مورد گزارش weka اکثر موارد مانند correctness rate ثابت است. البته ممکن است برای آموزش و تست سیستم از روش cross-validation استفاده شود، که در این روش شما در انتها یک جواب را مشاهده می کنید که در واقع میانگین جواب برای تست تعداد fold هایی است که برای تست انتخاب شده اند بعد از آموزش سیستم توسط بقیه نمونه ها.

مورد مهم بعدی در خروجی weka ، Incorrectly Classified Instances می باشد که تعداد و درصد نمونه هایی است که غلط طبقه بندی شده اند و سیستم (مدل) کلاس آن ها را به درستی شناسایی نکرده است.

Confusion Matrix نیز در خروجی weka قابل مشاهده می باشد، که برای بررسی دقیقتر مدل لازم است

Confusion Matrix ماتریس مربعی است که به تعداد کلاس ها سطر و ستون دارد، و اگر به طور مثال i عنصری قطر اصلی باشد در سطر و ستون j ، مقدار آن نشانگر تعداد نمونه هایی از کلاس j در data set می باشد که به درستی طبقه بندی شده اند، و اگر در سطر j مقدار سابرخانه ی سایر ستون ها که بر قطر اصلی نیستند غیر صفر باشد، به طور مثال خانه ای در سطر j و ستون k ، مقدار آن نشانگر تعداد نمونه های کلاس j است که به اشتباه در کلاس k توسط سیستم طبقه بندی شده اند. با بررسی این ماتریس می توان به طور دقیف فهمید که ضعف مدل در شناسایی چه کلاس هایی است و مدل توانسته چه کلاس هایی را به خوبی یاد گرفته و شناسایی کند، و یا اینکه چه کلاس هایی توسط مدل با هم اشتباه گرفته می شوند ، به این معنی که ممکن است تعداد زیادی از نمونه های یک کلاس در کلاس دیگر طبقه بندی شده باشند. ضعف سیستم در شناسایی یک کلاس ممکن است ناشی از انتخاب نمونه های بد برای آن کلاس باشد که نمایانگر الگوی رفتاری و خصوصیات آن کلاس نباشند، و یا ویژگی هایی که از نمونه ها استخراج شده اند ویژگی های خوبی نباشند، البته خروجی های ضعیف سیستم ممکن است دلایل دیگری نیز داشته باشد.

بسیاری از مواردی که در خروجی های weka دقیقا در قسمت بالای confusion matrix مشاهده می کنید از روی این ماتریس قابل محاسبه می باشد، برای آشنایی بیشتر با سایر موارد در گزارشات خروجی weka می توانید به manual آن مراجعه کنید که عموما در جایی که weka نصب شده کپی می شود.


۴ پیوست الف روشهای کاهش ویژگی

در این بخش یک مطالعه­ اجمالی برروی تمامی روشهای کاهش ویژگی[۱۲] انجام شده است که مشتمل بر دو دسته اصلی می باشد، روشهای مبتنی بر استخراج ویژگی و روشهای مبتنی بر انتخاب ویژگی.
۴٫۱ روشهای مبتنی بر استخراج ویژگی

همانطور که در بخش اول اشاره شد روشهای مبتنی بر استخراج ویژگی، یک فضای چند بعدی را به یک فضای با ابعاد کمتر نگاشت می­دهند. این روشها به دو دسته­ی خطی و غیرخطی تقسیم می­شوند. روشهای خطی که ساده­ترند و فهم آنها راحت­تر است بدنبال یافتن یک زیرفضای تخت عمومی (Global flat subspace) هستند. اما روشهای غیرخطی که مشکلترند و تحلیل آنها سخت­تر است بدنبال یافتن یک زیرفضای تخت محلی (Locally flat subspace) می­باشند.

از روشهای خطی می­توان به DFT، DWT، PCA و FA اشاره کرد که آنها را به ترتیب در ادامه­ی همین بخش توضیح خواهیم داد. روشهای دیگر غیرخطی عبارتند از:

    Projection Pursuit (PP) : برخلاف روشهای PCA و FA می­تواند اطلاعات بالاتر از مرتبه­ی دوم را ترکیب نماید. بنابراین روش مناسبی است برای بسترهای داده­ای غیر گاوسی.
    Independent Component Analysis (ICA) : این روش نیز یک نگاشت خطی انجام می­دهد اما بردارهای این نگاشت لزوماً بر یکدیگر عمود نیستند، در حالی که در روشهای دیگر مانند PCA این بردارها بر هم عمودند.
    Random Projection (PP) : یک روش ساده و در عین حال قدرتمند برای کاهش ابعاد داده است که از ماتریسهای نگاشت تصادفی برای نگاشت داده­ها به یک فضای با ابعاد کمتر استفاده می­کند.

از روشهای غیرخطی نیز می­توان به موارد زیر اشاره کرد:

    Principal Curves
    Self Organizing Maps
    Vector Quantization
    Genetic and Evolutionary Algorithms
    Regression

مسئله­ی کاهش ابعاد داده را بطور ریاضی می­توان به اینصورت بیان کرد: یک متغیر تصادفی p-بعدی  داریم. می­خواهیم متغیر k-بعدی را به گونه­ای پیدا کنیم که اولاً k ≤ p باشد و ثانیاً s محتویاتی که در x وجود دارد را بر اساس معیاری خاص دارا باشد. روشهای خطی سعی می­کنند هر یک از این k مؤلفه را از ترکیب خطی p مؤلفه­ی اولیه بدست آورند.

که Wk×p ماتریس وزنهای نگاشت خطی می­باشد.
Discrete Fourier Transform (DFT)

در بسیاری از کاربردها مرسوم است که از ترکیب توابع پایه­ای برای تقریب یک تابع استفاده شود. به عنوان مثال هر تابع پیوسته را می­توان توسط مجموعه­ای از توابع چند جمله­ای نمایش داد. تبدیل فوریه نوعی تبدیل است که یک تابع را بصورت توابع پایه­ای سینوسی که هر کدام در مقادیری ضرب شده­اند نشان می­دهد (شکل ۱). از تبدیل فوریه در بسیاری از زمینه­های علمی مانند فیزیک، هندسه، آمار و پردازش سیگنال استفاده می­شود.

 

شکل ۱- تبدیل فوریه سعی می­کند یک تابع را بصورت توابع پایه­ای سینوسی نشان دهد

تبدیل فوریه یک تبدیل برگشت پذیر است. این تبدیل می­تواند به دو صورت پیوسته یا گسسته انجام شود. در کامپیوتر و بخصوص در پردازش سیگنال معمولاً از تبدیل فوریه­ی گسسته (DFT) استفاده می­شود. خوشبختانه الگوریتمهای سریعی تحت عنوان FFT (Fast Fourier Transform) برای تبدیل فوریه­ی گسسته به وجود آمده است.
 Discrete Wavelet Transform (DWT)

تبدیل DWT برای اولین بار توسط شخصی به نام Alfred Haar بوجود آمد. تا کنون نسخه­های مختلفی برای DWT ارائه شده است، مانند Haar Wavelet، Newland Transform و Undecimated Wavelet Transform. این تبدیل نیز همانند تبدیل فوریه بسیار پرکاربرد است و در بسیاری از زمینه­های علوم و مهندسی مورد توجه قرار گرفته است. تبدیل Haar Wavelet بدلیل سادگی در پیاده سازی و سرعت اجرای بالا، از محبوبیت بیشتری نسبت به سایر نسخه­های DWT برخوردار است.

این تبدیل به اینصورت است که یک توالی به طول ۲n در ورودی داریم. این اعداد بصورت جفت جفت با هم جمع شده و این حاصل جمع­ها به مرحله­ی بعد فرستاده می­شوند. همچنین اختلاف هر جفت نیز محاسبه و ذخیره می­شود. دوباره این مرحله تکرار می­شود با این تفاوت که در ورودی، حاصل جمع جفتهای مرحله­ی قبل قرار می­گیرد. این فرایند بطور بازگشتی تکرار می­شود تا در نهایت یک عدد که حاصل جمع کل اعداد است بدست آید. این عدد به همراه ۲n-1 اختلاف جفتها که در مراحل مختلف الگوریتم محاسبه شده بعنوان خروجی این تبدیل بازگردانده می­شود.
Principal Component Analysis (PCA)

تکنیک PCA بهترین روش برای کاهش ابعاد داده به صورت خطی می­باشد. یعنی با حذف ضرایب کم­اهمیت بدست آمده از این تبدیل، اطلاعات از دست رفته نسبت به روشهای دیگر کمتر است. البته کاربرد PCA محدود به کاهش ابعاد داده نمی­شود و در زمینه­های دیگری مانند شناسایی الگو و تشخیص چهره نیز مورد استفاده قرار می­گیرد. در این روش محورهای مختصات جدیدی برای داده­ها تعریف شده و داده­ها براساس این محورهای مختصات جدید بیان می­شوند. اولین محور باید در جهتی قرار گیرد که واریانس داده­ها ماکسیمم شود (یعنی در جهتی که پراکندگی داده­ها بیشتر است). دومین محور باید عمود بر محور اول به گونه­ای قرار گیرد که واریانس داده­ها ماکسیمم شود. به همین ترتیب محورهای بعدی عمود بر تمامی محورهای قبلی به گونه­ای قرار می­گیرند که داده­ها در آن جهت دارای بیشترین پراکندگی باشند. در شکل زیر این مطلب برای داده­های دو بعدی نشان داده شده است.

 

 

روش PCA به نامهای دیگری نیز معروف است. مانند:

    Singular Value Decomposition (SVD)
    Karhunen Loeve Transform (KLT)
    Hotelling Transform
    Empirical Orthogonal Function (EOF)

Factor Analysis (FA)

FA یکی از روشهای آماری است که می­تواند چندین متغیر تصادفی مشاهده شده را توسط تعداد کمتری متغیر تصادفی (که در داده ها پنهان هستند) نمایش دهد. این متغیرهای تصادفی پنهان، فاکتور (factor) نامیده می شوند. این روش سعی می کند متغیرهای تصادفی مشاهده شده را توسط ترکیب خطی فاکتورها بعلاوه­ی مقداری خطا مدلسازی نماید. روش FA از رشته هوش سنجی سرچشمه گرفته و در زمینه­های علوم اجتماعی، بازاریابی، مدیریت تولید، تحقیق در عملیات و علوم کاربردی دیگر که با حجم بزرگی از داده­ها سروکار دارند مورد استفاده قرار گرفته است. این روش برای اولین بار حدود ۱۰۰ سال پیش توسط یک روانشناس به نام Charles Spearman ابداع شد. این شخص نظریه­ای به نام g theory ارائه داد و در آن ادعا کرد که تمام توانمندیهای ذهنی افراد مانند مهارتهای ریاضی، مهارتهای هنری، دایره لغات، توانایی استدلالهای منطقی و غیره را می­توان توسط یک فاکتور به نام هوش عمومی (General Intelligence) بیان کرد. البته این نظریه امروزه رد شده و تحقیقات انجام شده نشان می­دهد که توانمندیهای ذهنی حداقل از سه فاکتور به نامهای توانائی ریاضی، توانائی شفاهی و توانائی منطقی تشکیل شده است. روانشناسان زیادی بر این باورند که علاوه بر این سه فاکتور، فاکتورهای دیگری وجود دارد که می­تواند بر توانمندیهای ذهنی افراد تأثیرگذار باشد.
۴٫۲ روشهای مبتنی بر انتخاب ویژگی

مساله انتخاب ویژگی، یکی از مسائلی است که در مبحث یادگیری ماشین و همچنین شناسائی آماری الگو مطرح است. این مساله در بسیاری از کاربردها (مانند طبقه بندی) اهمیت به سزائی دارد، زیرا در این کاربردها تعداد زیادی ویژگی وجود دارد، که بسیاری از آنها یا بلااستفاده هستند و یا اینکه بار اطلاعاتی چندانی ندارند. حذف نکردن این ویژگی­ها مشکلی از لحاظ اطلاعاتی ایجاد نمی­کند ولی بار محاسباتی را برای کاربرد مورد نظر بالا می­برد. و علاوه بر این باعث می­شود که اطلاعات غیر مفید زیادی را به همراه داده­های مفید ذخیره کنیم.

برای مساله انتخاب ویژگی، راه حل­ها و الگوریتم­های فراوانی ارائه شده است که بعضی از آنها قدمت سی یا چهل ساله دارند. مشکل بعضی از الگوریتم­ها در زمانی که ارائه شده بودند، بار محاسباتی زیاد آنها بود، اگر چه امروزه با ظهور کامپیوترهای سریع و منابع ذخیره سازی بزرگ این مشکل، به چشم نمی­آید ولی از طرف دیگر، مجموعه­های داده­ای بسیار بزرگ برای مسائل جدید باعث شده است که همچنان پیدا کردن یک الگوریتم سریع برای این کار مهم باشد.

در این بخش ما در ابتدا تعاریفی که برای انتخاب ویژگی ارائه شده­اند و  همچنین، تعاریف مورد نیاز برای درک این مساله را ارائه می­دهیم. سپس روش­های مختلف برای این مساله را بر اساس نوع و ترتیب تولید زیرمجموعه ویژگی­های کاندید و همچنین نحوه ارزیابی این زیرمجموعه­ها دسته بندی می­کنیم. سپس تعدادی از روش­های معرفی شده در هر دسته را معرفی و بر اساس اهمیت، تا جائی که مقدور باشد، آنها را تشریح و الگوریتم برخی از آنها را ذکر می­کنیم. لازم به ذکر است که بدلیل اینکه مبحث انتخاب ویژگی به مبحث طبقه بندی بسیار نزدیک است، بعضی از مسائلی که در اینجا مطرح می­شود مربوط به مبحث طبقه بندی می­باشد. توضیحات ارائه شده برای الگوریتم­های مختلف در حد آشنائی است. شما می­توانید برای کسب اطلاعات بیشتر به منابع معرفی شده مراجعه کنید.

 
تعاریف

مساله انتخاب ویژگی بوسیله نویسندگان مختلف،  از دیدگاه­های متفاوتی مورد بررسی قرار گرفته است. هر نویسنده نیز با توجه به نوع کاربرد، تعریفی را از آن ارائه داده است. در ادامه چند مورد از این تعاریف را بیان می­کنیم[۶]:

    تعریف ایده­آل­: پیدا کردن یک زیرمجموعه با حداقل اندازه ممکن، برای ویژگی­ها است، که برای هدف مورد نظر اطلاعات لازم و کافی را در بر داشته باشد. بدیهی است که هدف تمام الگوریتم­ها و روش­های انتخاب ویژگی همین زیر مجموعه است.
    تعریف کلاسیک: انتخاب یک زیرمجموعه M عنصری از میان N ویژگی، به طوریکه M < N باشد و همچنین مقدار یک تابع معیار (Criterion Function) برای زیرمجموعه مورد نظر، نسبت به سایر زیرمجموعه­های هم­اندازه دیگر بهینه باشد. این تعریفی است که Fukunaga  و Narenda در سال ۱۹۷۷ ارائه داده­اند.
    افزایش دقت پیشگوئی: هدف انتخاب ویژگی این است که یک زیرمجموعه از ویژگی­ها برای افزایش دقت پیشگوئی انتخاب شوند. به عبارت دیگر کاهش اندازه ساختار بدون کاهش قابل ملاحظه در دقت پیشگوئی طبقه­بندی کننده­ای که با استفاده از ویژگیهای داده شده بدست می­آید.
    تخمین توزیع کلاس اصلی: هدف از انتخاب ویژگی این است که یک زیرمجموعه کوچک از ویژگی­ها انتخاب شوند، توزیع ویژگی­هایی که انتخاب می­شوند، بایستی تا حد امکان به توزیع کلاس اصلی با توجه به تمام مقادیر ویژگی­های انتخاب شده نزدیک باشد.

روش­های مختلف انتخاب ویژگی، تلاش می­کنند تا از میان N2 زیر مجموعه کاندید، بهترین زیرمجموعه را پیدا کنند. در تمام این روشها بر اساس کاربرد و نوع تعریف، زیر مجموعه­ای به عنوان جواب انتخاب می­شود، که  بتواند مقدار یک تابع ارزیابی را بهینه کند. با وجود اینکه هر روشی سعی می­کند که بتواند، بهترین ویژگی­ها را انتخاب کند، اما با توجه به وسعت جواب­های ممکن، و اینکه این مجموعه­های جواب بصورت توانی با N افزایش پیدا می­کنند، پیدا کردن جواب بهینه مشکل و در N های متوسط و بزرگ بسیار پر هزینه است.

به طور کلی روش­های مختلف انتخاب ویژگی را بر اساس  نوع جستجو به دسته های مختلفی تقسیم بندی می­کنند. در بعضی روش­ها تمام فضای ممکن جستجو می­گردد. در سایر روش­ها که می­تواند مکاشفه­ای و یا جستجوی تصادفی باشد، در ازای از دست دادن مقداری از کارآئی، فضای جستجو کوچکتر می­شود.

برای اینکه بتوانیم تقسیم بندی درستی از روش­های مختلف انتخاب ویژگی داشته باشیم، به این صورت عمل می­کنیم که فرآیند انتخاب ویژگی­ در تمامی روش­ها را به این بخش­ها تقسیم­ می­کنیم:

    تابع تولید کننده (Generation procedure): این تابع زیر مجموعه­های کاندید را برای روش مورد نظر پیدا می­کند.
    تابع ارزیابی (Evaluation function) : زیرمجموعه مورد نظر را بر اساس روش داده شده، ارزیابی و یک عدد به عنوان میزان خوبی روش باز می­گرداند. روش­های مختلف سعی در یافتن زیرمجموعه­ای دارند که این مقدار را بهینه کند.
    شرط خاتمه: برای تصمیم­گیری در مورد زمان توقف الگوریتم.
    تابع تعیین اعتبار (Validation procedure): تصمیم می­گیرد که آیا زیر مجموعه انتخاب شده معتبر است یا خیر؟

 

فرآیند انتخاب ویژگی

 

تابع تولید کننده در واقع تابع جستجو است. این تابع زیرمجموعه­های مختلف را به ترتیب تولید می­کند، تا بوسیله تابع ارزیابی، مورد ارزیابی قرا بگیرد. تابع تولید کننده از یکی از حالت­های زیر شروع به کار می­کند:

۱)     بدون ویژگی

۲)     با مجموعه تمام ویژگی­ها

۳)     با یک زیرمجموعه تصادفی

در حالت اول ویژگی­ها به ترتیب به مجموعه اضافه می­شوند و زیرمجموعه­های جدید را تولید می­کنند. این عمل آنقدر تکرار می­شود تا به زیر مجموعه مورد نظر برسیم. به اینگونه روش­ها، روشهای پائین به بالا می­گویند.در حالت دوم از یک مجموعه شامل تمام ویژگی­ها، شروع می­کنیم و به مرور و در طی اجرای الگوریتم، ویژگی­ها را حذف می­کنیم، تا به زیرمجموعه دلخواه برسیم. روش­هایی که به این صورت عمل می­کنند، روشهای بالا به پائین نام دارند.

یک تابع ارزیابی، میزان خوب بودن یک زیرمجموعه تولید شده را بررسی کرده و یک مقدار به عنوان میزان خوب بودن زیرمجموعه مورد نظر بازمی­گرداند. این مقدار با بهترین زیرمجموعه قبلی مقایسه می­شود. اگر زیر مجموعه جدید، بهتر از زیرمجموعه­های قدیمی باشد، زیرمجموعه جدید به عنوان زیرمجموعه بهینه، جایگزین قبلی می­شود.

 

   دسته بندی و تشریح الگوریتم های مختلف انتخاب ویژگی

در این قسمت بر اساس تابع ارزیابی و تابع تولید کننده، روش­های مختلف انتخاب ویژگی را به چند دسته تقسیم بندی می­کنیم و سپس تعدادی از روش­ها را شرح داده و الگوریتم کار را به صورت شبه کد، ذکر می­کنیم.

قبل از اینکه بحث را ادامه دهیم، لازم است که متغیرهای به کار رفته در شبه کدها را معرفی کنیم. این متغیرها و شرح آنها به صورت زیر می­باشد:

    D: مجموعه آموزشی
    S: مجموعه ویژگی اصلی (شامل تمام ویژگی­ها)
    N: تعداد ویژگی­ها
    T: زیرمجموعه ویژگی انتخاب شده
    M: تعداد ویژگی­های انتخاب شده یا تعداد ویژگی­هایی که لازم است انتخاب شوند.

 azsoftir.com
09367292276
09367292276
azsoftir@gmail.com
azsoftir.com
09367292276
09367292276
azsoftir@gmail.com
azsoftir.com

 الف) تابع ارزیابی مبتنی بر فاصله – تابع تولید کننده مکاشفه ای

مهمترین روش در این گروه Relief [8] است. در اینجا ما ابتدا این روش را به عنوان نماینده این گروه شرح می­دهیم، سپس یک مرور مختصری بر سایر روش­ها خواهیم داشت.

روش Relief از یک راه حل آماری برای انتخاب ویژگی استفاده می­کند، همچنین یک روش مبتنی بر وزن است که از الگوریتم­های مبتنی بر نمونه الهام گرفته است. روش کار به این صورت است که از میان مجموعه نمونه­های آموزشی، یک زیرمجموعه نمونه انتخاب می­کنیم. کاربر بایستی تعداد نمونه­ها(NoSample) در این زیرمجموعه را مشخص کرده باشد. و آنرا به عنوان ورودی به الگوریتم ارائه دهد. الگوریتم به صورت تصادفی یک نمونه از این زیرمجموعه­ را انتخاب می­کند، سپس برای هر یک از ویژگیهای این نمونه، نزدیکترین برخورد (Nearest Hit) و نزدیکترین شکست (Nearest Miss) را بر اساس معیار اقلیدسی پیدا می­کند. نزدیکترین برخورد نمونه­ای است که کمترین فاصله اقلیدسی را در میان سایر نمونه­های هم­کلاس با نمونه انتخاب شده دارد. نزدیکترین شکست نیز نمونه­ای است که کمترین فاصله اقلیدسی را در میان نمونه­هایی که هم­کلاس با نمونه انتخاب شده نیستند، دارد.

ایده اصلی در این الگوریتم این است که هر چه اختلاف بین اندازه یک ویژگی در نمونه انتخاب شده و نزدیکترین برخورد کمتر باشد، این ویژگی بهتر است و بعلاوه یک ویژگی خوب آن است که اختلاف بین اندازه آن ویژگی و نزدیکترین شکست وی بیشتر باشد. دلیل کار هم خیلی ساده است، ویژگی­هایی که به خوبی دو کلاس (یا یک کلاس از سایر کلاس­ها) را از هم تمییز می­دهند، برای نمونه­های متعلق به دو کلاس متفاوت مقادیری نزدیک به­هم نمی­دهند و یک فاصله معنی­داری بین مقادیری که به نمونه­های یک کلاس می­دهند و مقادیری که به سایر کلاس(ها) می­دهند وجود دارد.

الگوریتم پس از تعیین نزدیکترین برخورد و نزدیکترین شکست، وزن­های ویژگی­ها را به روزرسانی می­کند، این به­روز­رسانی به این صورت است که مربع اختلاف بین مقدار ویژگی مورد نظر در نمونه انتخاب شده و نمونه نزدیکترین برخورد از وزن ویژگی کم می­شود و در عوض مربع اختلاف بین مقدار ویژگی در نمونه انتخاب شده و نزدیکترین شکست به وزن ویژگی اضافه می­شود. هر چه مقدار این وزن بزرگتر باشد، ویژگی مورد نظر، بهتر می­تواند نمونه­های یک کلاس را از دیگران جدا کند.

بعد از تعیین فاصله برای تمام نمونه­های موجود در مجموعه نمونه­ها، الگوریتم ویژگی­هایی را که وزن آنها کمتر یا مساوی با یک حد آستانه­ای است، را حذف می­کند، و سایر ویژگی­ها بعنوان زیرمجموعه ویژگی جواب باز می­گردند. مقدار حد آستانه­ای توسط کاربر تعیین می­گردد، البته ممکن است که بصورت اتوماتیک بوسیکه یک تابعی از تعداد کل ویژگی­ها تعیین شود و یا اینکه با سعی و خطا تعیین گردد. همچنین می­توان ویژگی­هایی که وزن آنها منفی است را حذف کرد.

 

 
azsoftir.com
09367292276
09367292276
azsoftir@gmail.com
azsoftir.com
09367292276
09367292276
azsoftir@gmail.com
azsoftir.com
 

الگوریتم Relief

الگوریتم Relief برای ویژگی­های دارای نویز یا ویژگی­های دارای همبستگی خوب کار می­کند و پیچیدگی زمانی آن بصورت خطی و تابعی از تعداد ویژگی­ها و تعداد نمونه­های مجموعه نمونه می­باشد. و هم برای داده­های پیوسته و هم برای داده­های صوری خوب کار می­کند.

یکی از محدودیت­های اساسی این الگوریتم این است که ویژگی­هایی که دارای افزونگی باشند را پیدا نمی­کند و بنابراین مجموعه­های غیر بهینه را پیدا می­کند که دارای افزونگی هستند. این مشکل را می­توان با یک جستجوی تعیین جامعیت برای زیرمجموعه­های تولید شده توسط الگوریتم حل کرد. علاوه بر این مشکل دیگر این الگوریتم این است که با مسائل دو کلاسه خوب کار می­کند. این محدودیت نیز با الگوریتم Relief-F [9] مرتفع شده است، با الگوریتم جدید مشکل داده­های غیر کامل (نمونه­های آموزشی غیرکامل) نیز حل شده است.

روشی که Jakub Segen [10] برای انتخاب ویژگی مطرح کرده است، از یک تابع ارزیابی استفاده می­کند که مجموع یک معیار اختلاف آماری و یک معیار پیچیدگی ویژگی را محاسبه کرده و آنرا مینیمم می­کند. این الگوریتم، اولین ویژگی را که بهتر بتواند کلاس­ها را از هم تمییز دهد را پیدا می­کند. سپس ویژگی­هایی را پیدا می­کند، که در ترکیب با ویژگی­های انتخاب شده، جدائی­پذیری کلاس­ها را افزایش دهند. این فرآیند زمانی متوقف می­شود که به حداقل معیار بازنمائی مورد انتظار برسیم.

 

ب)  تابع ارزیابی مبتنی بر فاصله – تابع تولید کننده کامل

استفاده از این ترکیب در روش­های قدیمی نظیر B&B (Branch and Bound) یافت می­شود. سایر روش­های این گروه، نسخه­های متفاوتی از B&B هستند. به این ترتیب که یا یک تابع تولید کننده دیگری را استفاده کرده­اند (BFF [11]) و یا اینکه از یک تابع ارزیابی متفاوتی استفاده کرده­اند (Bobrowski’s method [12]). در اینجا ابتدا به شرح B&B می­پردازیم و سپس یک شرح مختصری در مورد دو روش دیگر ارائه می­دهیم.

تعریف کلاسیک ارائه شده بوسیله Fukunaga  و Narenda از انتخاب ویژگی، احتیاج دارد که تابع ارزیابی یکنوا باشد. یعنی اگر دو زیرمجموعه ویژگی A و B با اندازه­های M و N موجود باشند، و B A در اینصورت مقدار تابع ارزیابی برای A نباید بیشتر از مقدار تابع برای B باشد. این تعریف باعث ایجاد مشکل در مسائل دنیای واقعی می­شود، زیرا اندازه تخمینی زیرمجموعه ویژگی بهینه در حالت عمومی ناشناخته است.

البته به سادگی می­توان این تعریف را تغییر داد تا با مسائل عمومی سازگار شود، به اینصورت که می­گوئیم: الگوریتم­های مشابه B&B تلاش می­کنند که دو شرط زیر را همزمان ارضاء کنند:

    زیرمجموعه ویژگی جواب تا حد امکان کوچک باشد.
    یک کران برای مقدار تابع ارزیابی را در نظر بگیرد. (یا یک اندازه مینیمم برای تعداد ویژگی­های انتخاب شده مثلاً بهترین زیرمجموعه ویژگی سه عنصری)

بوسیله کران تعیین شده، فضای جستجو تا حد امکان کوچک می­شود. به این ترتیب الگوریتم B&B از  یک زیرمجموعه شامل تمام ویژگی­های موجود شروع می­کند و درخت جستجو را تشکیل می­دهد. در این درخت در ریشه تمام ویژگی­ها قرار دارند و فرزندان وی، زیرمجموعه­هایی هستند که زیرمجموعه، گره پدر هستند و از حذف تنها یکی از عناصر پدرشان تشکیل شده­اند. این روند برای سایر گره­های درخت تکرار می­شود تا به مجموعه­ها تک عنصری (یا تعداد ویژگی­های تعیین شده بعنوان کران) برسیم. یعنی برگ­های درخت مجموعه­های تک عنصری هستند و ریشه درخت یک مجموعه شامل همه ویژگی­های موجود.

با توجه به این خاصیت که تمام زیرمجموعه­های یک مجموعه مقدار کمتری برای تابع ارزیابی دارند، در حین جستجو اگر یک گره به واسطه کم بودن مقدار تابع ارزیابی انتخاب نشد، زیرشاخه­های آنرا برای یافتن جواب جستجو نمی­کنیم، چون قطعاً تابع ارزیابی مقدار کمتری را برای آنها باز می­گرداند.
azsoftir.com
09367292276
09367292276
azsoftir@gmail.com
azsoftir.com
09367292276
09367292276
azsoftir@gmail.com
azsoftir.com
عموماً توابع ارزیابی زیر برای اینکار استفاده می­شوند:

    فاصله ماهالانوبیس (Mahalanobis Distance)
    تابع جداساز (Discriminant Function)
    معیار فیشر (Fisher Criterion)
    فاصله باتاچاریا (Bhattacharya)
    Divergence

یک الگوریتم مشابه برای انتخاب ویژگی BFF است، در این الگوریتم، تابع جستجو به این صورت تغییر کرده است که مشابه حل مساله جستجوی یک مسیر بهینه در یک درخت وزن­دار با یک استراتژی تغییر یافته از Best first search است. این الگوریتم تضمین می­کند که بهترین هدف(زیرمجموعه بهینه) بدون از دست دادن جامعیت مساله پیدا شود، البته با ارضای معیار یکنوا بودن تابع ارزیابی.

 

 

ج) تابع ارزیابی مبتنی بر اطلاعات – تابع تولید کننده مکاشفه ­ای – در این دسته دو روش وجود دارد:

۱)   روش درخت تصمیم

در روش درخت تصمیم، نمونه­ها به یک الگوریتم C4.5­[۱۵]، که یکی از درختهای تصمیم­گیری است اعمال می­شوند، سپس درخت هرس شده حاصل از الگوریتم C4.5 را گرفته و کلیه ویژگی­هایی که در آن وجود دارد را بعنوان جواب مساله باز می­گردانیم.

الگوریتم C4.5، از یک تابع مکاشفه بر پایه اطلاعات استفاده می­کند، یک فرم ساده این توابع برای مسائل دو کلاسه به صورت زیر است:

 

 

که در آن p  تعداد نمونه­های کلاس اول و n تعداد نمونه­های کلاس دوم است. فرض کنید که صفت F1 بعنوان ریشه درخت در نظر گرفته شده است و مجموعه آموزشی را به دو زیرمجموعه T1 و T0 تقسیم کرده است. آنتروپی ویژگی F1 برابر است با:

الگوریتم درخت تصمیم به صورت زیر است[۱۳]:
azsoftir.com
09367292276
09367292276
azsoftir@gmail.com
azsoftir.com
09367292276
09367292276
azsoftir@gmail.com
azsoftir.com
الگوریتم درخت تصمیم

د)تابع ارزیابی مبتنی بر اطلاعات – تابع تولید کننده کامل

مهمترین روشی که در این گروه می­توانیم پیدا کنیم، روش Minimum Description Length Method (MDLM) است[۱۶]. نویسندگان این روش تلاش می­کنند تا همه ویژگی­های بدون استفاده (بی­ربط یا اضافی) را حذف نمایند، با این دید که اگر ویژگی­های زیرمجموعه V را بتوانیم بصورت یک تابع ثابتی مانند F که وابسته به کلاس نیست، بر اساس یک زیرمجموعه ویژگی دیگر مانند U بیان کنیم. در این صورت وقتی که مقادیر ویژگی­های زیرمجموعه U شناخته شده باشند، ویژگی­های موجود در زیرمجموعه V بدون استفاده هستند.

از دیدگاه انتخاب ویژگی، اجتماع دو زیرمجموعه U و V، مجموعه کامل، شامل تمام ویژگی­ها را تشکیل می­دهد. و کاری که ما باید در انتخاب ویژگی انجام دهیم این است که این دو زیرمجموعه را جدا کنیم. برای انجام این کار، نویسندگان MDLM، از معیار Minimum Description Length Criterion (MDLC) که بوسیله Rissanen ارائه شده است[۱۷]، استفاده کرده­اند. آنها فرمولی را بدست آورده­اند، که شامل تعداد بیتهای لازم برای انتقال کلاسها، پارامترهای بهینه سازی، ویژگی­های مفید و ویژگی­های غیرمفید است. الگوریتم تمام زیرمجموعه­های ممکن (۲N) جستجو می­کند و بعنوان خروجی زیرمجموعه­ای را بازمی­گرداند که معیار MDLC را ارضا کند. این روش می­تواند تمام ویژگی­های مفیدی را پیدا کند که دارای توزیع نرمال باشند. برای حالتهای غیر نرمال این روش قادر نیست، ویژگی­های مفید را پیدا کند. الگوریتم زیر روش کار و فرمول­های استفاده شده را نشان می­دهد.

الگوریتم روش Minimum Description Length Method (MDLM)

و) تابع ارزیابی مبتنی بر وابستگی – تابع تولید کننده مکاشفه ­ای

دو روش عمده در این گروه وجود دارد :

Probability of Error & Average Correlation Coefficient (POE1ACC)

که خود شامل هفت روش است[۱۸]، ما در اینجا روش هفتم را که به گفته نویسنده کاملتر است را بررسی می­کنیم. در این روش اولین ویژگی به این صورت تعیین می­شود که احتمال خطا را برای تمام ویژگی­ها محاسبه می­کنیم، ویژگی با کمترین احتمال خطا (Pe)، به عنوان اولین ویژگی انتخاب می­شود. ویژگی بعدی، آن ویژگی است که مجموع وزن­دار Pe و میانگین ضریب همبستگی(ACC) با ویژگی(های) انتخاب شده را مینیمم کند.  سایر ویژگی­ها به همین ترتیب انتخاب می­شوند. میانگین ضریب همبستگی به اینصورت است که میانگین ضریب همبستگی ویژگی کاندید با ویژگی­های انتخاب شده در آن نقطه محاسبه می­شوند.

 
azsoftir.com
09367292276
09367292276
azsoftir@gmail.com
azsoftir.com
09367292276
09367292276
azsoftir@gmail.com
azsoftir.com
الگوریتم Probability of Error & Average Correlation Coefficient (POE1ACC)

این روش می­تواند تمام ویژگی­ها را بر اساس مجموع وزن­دار درجه­بندی کند. شرط خاتمه نیز در این روش تعداد ویژگی­های مورد نیاز خواهد بود.

برای اینکه یک جمع­بندی از کلیه روش­های انتخاب ویژگی داشته باشیم، نمودار آنها را برحسب سه نوع تابع تولید کننده در شکل زیر نشان داده­ایم.

سپس برای اینکه داده­هایی که به صورت کنترل نشده جمع­آوری شده­اند و بعضی از آنها وابستگی به دیگری دارند را از محاسبات خود خارج نموده و نتایج را به شکل دقیقتری داشته باشیم از نوع دیگر فیلتر استفاده می­کنیم که با الگوریتم­های متفاوتی که دارند می­توانند این عمل را برای ما انجام دهند .
۵ پیوست ب : روشهای داده کاوی و شناسایی الگو و پیشبینی
۵٫۱ دسته­بندی/ طبقه بندی [۱۳]

دسته­بندی در واقع ارزشیابی ویژگیهای مجموعه ای از داده­ها و سپس اختصاص دادن آنها به مجموعه­ای از گروههای از پیش تعریف شده است. این متداولترین قابلیت داده کاوی می باشد. داده کاوی را می توان با استفاده از داده های تاریخی برای تولید یک مدل یا نمایی از یک گروه بر اساس ویژگی های داده ها به کار برد. سپس می توان از این مدل تعریف شده برای طبقه بندی مجموعه داده های جدید استفاده کرد. همچنین می توان با تعیین نمایی که با آن سازگار است برای پیش بینی های آتی ازآن بهره گرفت.در دنیای امروز بحث classification اطلاعات اهمیت بسیاری دارد،اینکه بتوان مدلی مناسب برای تحلیل داده هایی خاص بدست آورد و بتوان با بررسی اولیه ویژگی های یک عنصر خاص ، الگوی رفتاری آن عنصر را پیش بینی کرد .

 

 

در مسائل دسته­بندی هدف شناسایی ویژگیهایی است که گروهی را که هر مورد به آن تعلق دارد را نشان دهند. از این الگو می­توان هم برای فهم داده­های موجود و هم پیش­بینی نحوه رفتار مواد جدید استفاده کرد.

در داده کاوی مبحث طبقه بندی اطلاعات به بررسی اینگونه مدل ها و متد ها می پردازد. در دسته­بندی اطلاعات هدف بدست آوردن مدلی برای الگوی رفتاری و ویژگی های مجموعه ایی از داده ها است تا با کمک آن بتوان بدون دانستن رفتار یک موجودیت، با توجه به ویژگی های آن و با استفاده از مدل بدست آورده شده، رفتار آن را تشخیص داد و آن موجدیت را در گروه خاصی طبقه بندی کرد . امروزه شرکت های بسیار زیادی در سراسر نقاط جهان با استفاده از این علم به تحلیل،بررسی و پیش بینی رفتار مشتریان خود می پردازند . داده­کاوی مدلهای دسته­بندی را با بررسی داده­های دسته­بندی شده قبلی ایجاد می­کند و یک الگوی پیش­بینی کننده را بصورت استقرایی می­یابند. این موارد موجود ممکن است از یک پایگاه داده تاریخی آمده باشند.

در واقع سیستم هایی که بر اساس دسته­بندی ، داده کاوی می کنند، دو مجموعه ورودی دارند: یک مجموعه آموزشی که در آن داده هایی که به طور پیش فرض در دسته های مختلفی قرار دارند، همراه با ساختار دسته بندی خود وارد سیستم می شوند و سیستم بر اساس آ نها به خود آموزش می دهد یا به عبارتی پارامترهای دسته بندی را برای خود مهیا می کند.
azsoftir.com
09367292276
09367292276
azsoftir@gmail.com
azsoftir.com
09367292276
09367292276
azsoftir@gmail.com
azsoftir.com
دسته دیگر از ورودی هایی هستند که پس از مرحله آموزش وبرای تعیین دستهوارد سیستم می شوند.
داده کاوی مدلهای دسته­بندی را بوسیله امتحان کردن داده طبقه بندی شده(موارد) و نهایتا یافتن یک الگوی پیش گو ایجاد می کند. این موارد موجود می تواند از یک پایگاه داده تاریخی ناشی شود مانند اطلاعات افرادی که تحت معالجه دارویی خاصی هستند و یا به سمت یک خدمت با مسافت دور جذب شده اند.یا اینکه از تجربه هایی که طی آن یک نمونه از تمام پایگاه داده در جهان واقعی تست شده باشد و نتایج آن برای ایجاد یک گروه بند استفاده شده باشند منتج شود.

از جمله تکنیک های داده کاوی که برای طبقه بندی به کار می آیند می توان از تکنیک های شبکه عصبی و درخت تصمیم گیری و KNN نام برد، طبقه بندی یکی از انواع یاد گیری با نظارت است.
۵٫۲ رگرسیون[۱۴]

رگرسیون از مقادیر موجود برای پیش­بینی مقادیر دیگر استفاده می­کند. در ساده­ترین فرم، رگرسیون از تکنیک­های آماری استاندارد مانند رگرسیون خطی استفاده می­کند. متاسفانه، بسیاری مسائل دنیای واقع تصویرخطی ساده­ای از مقادیر قبلی نیستند. بناراین تکنیک­های پیچیده­تری مانند رگرسیون منطقی ، درخت­های تصمیم و یا شبکه­های عصبی ممکن است برای پیش­بینی مورد نیاز باشند.
۵٫۳ رگرسیون منطقی

رگرسیون منطقی یک حالت عمومی تر از regression خطی می باشد.قبلا این روش برای پیش بینی مقادیر باینری یا متغیرهای دارای چند مقدار گسسته (کلاس) استفاده می شد. از آنجایی که مقادیر مورد نظر برای پیش بینی مقادیر گسسته می باشند نمی توان آنرا به روش regression خطی مدلسازی کرد برای این منظور این متغیرهای گسسته را به روشی تبدیل به متغیر عددی و پیوسته می کنیم وبرای این منظور مقدار لگاریتم احتمال متغیر مربوطه را در نظر می گیریم و برای این منظور احتمال پیشامد را بدین صورت در نظر می گیریم :     احتمال اتفاق نیفتادن پیشامد/ احتمال اتفاق افتادن پیشامد

و تفسیر این نسبت مانند تفسیری است که در بسیاری از مکالمات روزمره در مورد مسابقات یا شرط بندی ها ی موارد مشابه به کار می رود .مثلا وقتی می گوییم شانس بردن یک تیم در مسابقه ۳ به ۱ است در واقع از همین نسبت استفاده کرده و معنی آن این است که احتمال برد آن تیم ۷۵% است.
۵٫۴ پیش بینی سری های زمانی

پیش­بینی های Time series مقادیر ناشناخته آینده را براساس یک سری از پیش­بینی گرهای متغیر با زمان پیش­بینی می­کنند. و مانند رگرسیون ، از نتایج دانسته شده برای راهنمایی پیش­بینی خود استفاده می­کنند. مدلها باید خصوصیات متمایز زمان را در نظر گیرند و بویژه سلسله­مراتب دوره­ها را. انواع مدل یکسانی را می­توان هم برای رگرسیون و هم برای دسته­بندی استفاده کرد. برای مثال الگوریتم درخت تصمیم CART را می­توان هم برای ساخت درخت­های دسته­بندی و هم درخت­های رگرسیون استفاده کرد. شبکه­های عصبی را نیز می­توان برای هر دو مورد استفاده کرد .
۵٫۵ تفاوت دسته­بندی و رگرسیون

این دو روشهای مهمی در آمار هستند.هر دو با پیشگویی جواب متغیر y که مقدارش را از بردار پیشگوی متغیر x می گیرد شروع می کنند.X دامنه x وY دامنه y را مشخص می کند.اگر یک متغیر پیوسته یا نا پیوسته y مقدار حقیقی بگیرد (به عنوان مثال وزن ماشینها و یا تعداد تصادفات) مساله رگرسیون نامیده می شود.در غیر این صورت ، اگر Y یک مجموعه نا متناهی از متغیر های نا مرتب باشد ،(مانند نوع ماشینها و یا کشور سازنده آنها) مساله دسته­بندی است.در اصطلاح ریاضی مساله یافتن تابع d(x) است که نگاشت هر نقطه در مجموعه X را به نقطه ای در مجموعه Y انجام دهد.ساختمان d(x) نیاز به وجود یک مثال train شده از n مشاهده L = {(x1, y1), . . . , (xn, yn)} دارد. در علم کامپیوتر ، این موضوع با عنوان یادگیری با نظارت   supervised learning) شناخته می شود. معیار انتخاب d(x) معمولابر پایه توان ۲ محاسبه خطا E{d(x)−E(y|x)}2 برای رگرسیون است و جاییکه که E(y|x) امید ریاضی y در xو ارزش مورد نظر misclassification باشد، برای دسته­بندی است. اگر Y شامل J مقدار مجزا باشد،راه حل دسته­بندی یا دسته­بندی ممکن است به عنوان یک افراز از X در J بخش گسسته Aj = {x : d(x) = j} که است نوشته شود.یک درخت classification یک نوع خاص از classifier است جاییکه هر Aj خودش یک اجتماع از مجموعه ها با مجموعه هایی که از تفکیک بازگشتی x-space برست می آیند، باشد.این به classifier اجازه می دهد که مانند یک درخت تصمیم نشان داده شود.یک درخت رگرسیون شبیه یک درخت راه حل ساخت یافته در هریک مقدار ثابت ویا یک مدل نسبتا ساده رگرسیون است که داده های هر بخش جفت و جور شده باشد، است .یک الگوریتم درخت رگرسیون یا classification 3 بخش مهم دارد :

    چگونگی تفکیک داده ها هر بخش
    زمان توقف تفکیک
    چگونگی پیش گویی مقدار y برای هر x در یک تفکیک

شیوه های زیادی برای بخش اول وجود دارد . برای سهولت تفسیر اکثریت زیادی از الگوریتم ها انشعاب یک متغیزه از نوع xi ≤ c (اگر xi غیر قطعی باشد) یا (اگر xi قظعی باشد).متغیر xi و نقطه انشعاب c یا مجموعه انشعاب B گاهی بوسیله یک جستجوی فراگیر که معیاریک نود خارجی را بهینه می کند مانند entropy (برای classification )یا مجموع مربعات باقیمانده(برای رگرسیون )پیدا می شوند.همچنین راههای زیادی برای بخش روم وجود دارد مانند قوانین توقف و هرس درخت.بخش سوم ساده ترین بخش است:مقدار پیش گویی شده y در یک نود برگ یک کلاس است که هزینه تخمین misclassification (برای دسته­بندی ) مینیمم می کند یا مقدار مناسب را از یک مدل تخمین در نود (برای رگرسیون ) می آورد.
۵٫۶ خوشه‌بندی[۱۵]
azsoftir.com
09367292276
09367292276
azsoftir@gmail.com
azsoftir.com
09367292276
09367292276
azsoftir@gmail.com
azsoftir.com
خوشه‌بندی را می‌توان به عنوان مهمترین مسئله در یادگیری بدون نظارت در نظر گرفت. خوشه‌بندی با یافتن یک ساختار درون یک مجموعه از داده‌های بدون برچسب درگیر است. خوشه‌ به مجموعه‌ای از داده‌ها گفته می‌شود که به هم شباهت داشته باشند. در خوشه‌بندی سعی می‌شود تا دادهها به خوشه‌هایی تقسیم شوند که شباهت بین داده‌های درون هر خوشه حداکثر و شباهت بین داده‌های درون خوشه‌های متفاوت حداقل شود. در این شکل نمونه‌ای از اعمال خوشه‌بندی روی یک مجموعه از داده‌ها مشخص شده است که از معیار فاصله(Distance) به عنوان عدم شباهت(Dissimilarity) بین داده‌ها استفاده شده است.

در طبقه‌بندی هر داده به یک طبقه (کلاس) از پیشین مشخص شده تخصیص می‌یابد ولی در خوشه‌بندی هیچ اطلاعی از کلاسهای موجود درون داده‌ها وجود ندارد و به عبارتی خود خوشه‌ها نیز از داده‌ها استخراج می‌شوند. در شکل زیر تفاوت بین خوشه‌بندی و طبقه‌بندی بهتر نشان داده شده است. در طبقه‌بندی با استفاده  یک سری اطلاعات اولیه داده‌ها به دسته‌های معلومی نسبت داده‌ می‌شوند. در خوشه‌بندی داده‌ها با توجه به الگوریتم انتخاب شده به خوشه‌هایی نسبت داده‌ می‌شوند.

 

 

 
۵٫۷ الگوریتم های دسته­بندی : درخت تصمیم گیری و K-NN
۵٫۷٫۱ درخت تصمیم گیری/ درخت تصمیم[۱۶]

یکی دیگر از الگوریتم های دسته­بندی ، درخت تصمیم گیری یاDecision Tree  است که مدل خود را بر اساس یک درخت پیاده سازی می کند . در این الگوریتم با توجه به مجموعه آموزش یک درخت بر اساس ویژگی های مختلف آن درست می شود که با استفاده از این درخت باید بتوان یک عضو جدید را در دسته خاصی طبقه بندی کرد .

با جستجو در گره های درخت( که در هر گره شرطی بررسی می شود تا مسیر بعدی خودمان را پیدا کنیم) میتوانیم به یک برگ برسیم که آن برگ مشخص کننده نوع عضو جدید ما است. ریشه درخت محل آغازین پیمایش درخت است که به بررسی اولین متغیر می پردازد. گره ها نیز مثل ریشه به بررسی متغیر ها می پردازد. نتیجه بررسی آن است که با شاخه های آن گره به گره دیگری برود و یا به برگ برسد. برگ ها پایان درخت هستند. نقاطی که وضعیت داده را مشخص می کند.

براساس الگوریتم، ممکن است دو یا تعداد بیشتری شاخه داشته باشد. برای مثال، CART درختانی با تنها دو شاخه در هر نود ایجاد می­کند. هر شاخه منجر به نود تصمیم دیگر یا یک نود برگ می­شود. با پیمایش یک درخت تصمیم از ریشه به پایین به یک مورد یک رده یا مقدار نسبت می­دهیم. هر نود از داده­های یک مورد برای تصمیم­گیری درباره آن انشعاب استفاده می­کند. درخت­های تصمیم از طریق جداسازی متوالی داده­ها به گروه­های مجزا ساخته می­شوند و هدف در این فرآیند افزایش فاصله بین گروه­ها در هر جداسازی است.یکی از تفاوت­ها بین متد­های ساخت درخت تصمیم این است که این فاصله چگونه اندازه­گیری می­شود. درخت­های تصمیمی که برای پیش­بینی متغیرهای دسته­ای استفاده می­شوند، درخت­های classification نامیده می­شوند زیرا نمونه­ها را در دسته­ها یا رده­ها قرار می­دهند. درخت­های تصمیمی که برای پیش­بینی متغیرهای پیوسته استفاده می­شوند درخت­های رگرسیون نامیده می­شوند.

هر مسیر در درخت تصمیم تا یک برگ معمولا قابل فهم است. از این لحاظ یک درخت تصمیم می­تواند پیش­بینی­های خود را توضیح دهد، که یک مزیت مهم است. با این حال این وضوح ممکن است گمراه­کننده باشد. برای مثال، جداسازی های سخت در درخت­های تصمیم دقتی را نشان می­دهند که کمتر در واقعیت نمود دارند. (چرا باید کسی که حقوق او ۴۰۰۰۰۱ است از نظر ریسک اعتبار خوب باشد درحالیکه کسی که حقوقش ۴۰۰۰۰ است بد باشد. بعلاوه، از آنجاکه چندین درخت می­توانند داده­های مشابه­ای را با دقت مشابه نشان دهند، چه تفسیری ممکن است از قوانین شود؟

درخت­های تصمیم تعداد دفعات کمی از داده­ها گذر می­کنند(برای هر سطح درخت حداکثر یک مرتبه) و با متغیرهای پیش­بینی­کننده زیاد بخوبی کار می­کنند. درنتیجه، مدلها بسرعت ساخته می­شوند، که آنها را برای مجموعه­داده های بسیار مناسب می­سازد. اگر به درخت اجازه دهیم بدون محدودیت رشد کند زمان ساخت بیشتری صرف می­­شود که غیرهوشمندانه است، اما مسئله مهمتر اینستکه با داده­ها overfit می­شوند. اندازه درخت­ها را می­توان از طریق قوانین توقف کنترل کرد. یک قانون معمول توقف محدود کردن عمق رشد درخت است.

راه دیگر برای توقف هرس کردن درخت است. درخت می­تواند تا اندازه نهایی گسترش یابد، سپس با استفاده از روش­های اکتشافی توکار یا با مداخله کاربر، درخت به کوچکترین اندازه­ای که دقت در آن از دست نرود کاهش می­یابد. یک اشکال معمول درخت­های تصمیم اینستکه آنها تقسیم­کردن را براساس یک الگوریتم حریصانه انجام می­دهند که در آن تصمیم­گیری اینکه براساس کدام متغیر تقسیم انجام شود، اثرات این تقسیم در تقسیم­های آینده را درنظر نمی­گیرد. بعلاوه الگوریتم­هایی که برای تقسیم استفاده می­شوند، معمولا تک­متغیری هستند: یعنی تنها یک متغیر را در هر زمان در نظر می­گیرند. درحالیکه این یکی از دلایل ساخت سری مدل است، تشخیص رابطه بین متغیرهای پیش­بینی کننده را سخت­تر می­کند.
۵٫۷٫۲ K-nearest neighbor

یکی از الگوریتمهای طبقه بندی می باشد . مبنای الگوریتم KNN پیدا کردن تعداد معینی از نزدیکترین عناصر موجود در جامعه آماری به عنصر جدید واردشده در آن جامعه است که بر اساس آن بتوان نزدیکترین داده  (داده ها) موجود به عنصر جدید را از لحاظ ویژگی های مختلف پیدا کرد تا عنصر جدید را در همان طبقه ای قرار داد که عناصر نزدیک به آن قرار دارند. Knn یکی از روش های غیر پارامتریک برای بدست آوردن تابع توزیع از روی داده های توزیع شده می باشد. همچنین این روش یکی از متداول ترین روش ها برای دسته بندی داده ها می باشد.

در بالابه بررسی تعدادی از روشهای به کار گرفته شده و توضیحات مرتبط با آن پرداخته شد جهت دسترسی به اطلاعات تکمیلی بهمنابع مراجعه نمایید.
۶ پیوست ج: استخراج خصوصیات نرمافزارهای مضر/ملور ها به منظور بازنمایی رفتار آنها- توضیحات تکمیلی
azsoftir.com
09367292276
09367292276
azsoftir@gmail.com
azsoftir.com
09367292276
09367292276
azsoftir@gmail.com
azsoftir.com
تمامی مواردی که در ادامه می آید در فایلهای XML دانلود شده قابل پیگیری است .در ابتدا یک سری DLL از تمامی فایلها که بیشترین تعداد تکرار را داشت انتخاب گردید ، در زیر میتوانید لیست تجربی از تعداد تکرارها (Quantity) در dll ها را که به دست آمده مشاهده نمایید.

“version.dll”, “authz.dll”, “crypt32.dll”, “msan1.dll”, “nddeapi.dll”, “profmap.dll”, “netapt32.dll”, “psapi.DLL”, “regapi.dll”, “seupapiI.dll”, “winsta.dll”, “wintrust.dll”, “imagehlp.dll”, “ws2_32.dll”, “ws2help.dll”, “msgina.dll”, “cimctl32.dll”, “odbc32.dll”, “comdlg32.dll”, “odbcint.dll”, “shsvcs.dll”, “sfc.dll”, “sfc_os.dll”, “apphelp.dll”, “winscard.dll”, “wtsapi32.dll”, “sxs.dll”, “cscdll.dll”, “winotify.dll”, “mpr.dll”, “winspool.DRV”, “wgalogon.dll”, “rsaenh.dll”, “ntmarta.dll”, “samltb.dll”, “wldap32.dll”, “clbcatq.dll”, “comres.dll msv1_0.dll”, “iphlpapi.dll”, “cscui.dll”, “xpsp2res.dll”, “wsock32.dll”, “wininet.dll”, “rasapi32.dll”, “rtutils.dll”, “ntdll.dll”, “kernel32.dll”, “user32.dll”, “gdi32.dll”, “advapi32.dll”, “rpcrt4.dll”, “secur32.dll”, “oleaut32.dll”, “msvcrt.dll”, “ole32.dll”, “pstorec.dll”, “atl.dll”, “uxtheme.dll”, “msctfime.ime”, “msctf.dll”, “shimEng.dll”, “winmm.dll”, “msacm32.dll”, “shell32.dll”, “shlwapt.dll”, “userenv.dll”, “comctl32.dll”, “rbzltyqdzwskr.deu”, _

“rbzltyqdzwskr.de”, “olepro32.dll”, “rbzltyqdzwskr.dll”, “urlmon.dll”, “iertutil.dll”, “imm32.dll”,   “rasman.dll”, “ieframe.dll”, “mshtml.dll”, “msimtf.dll”, “mlang.dll”, “usp10.dll”, “apphelp.dll”, “asycfil.de”, “asycfil.dll”

 

در ادامه لیستی از تعداد تکرارها (Quantity) مشخصات فایلهای که باز میشوند یا دستکاری میگردند و همچنین ایجاد فرایندها و موتکسها و.. در نظر گرفته شد لیست آنها به صورت XML را در زیر مشاهده میکنید.

Elements.<process>.<filesystem_section>.<open_file>

Elements.<process>.<filesystem_section>.<find_file>

Elements.<process>.<mutex_section>.<create_mutex>

Elements.<process_call>.<calltree>.<process_call>

البته این لیست در آزمایشات متفاوت اندکی تغییرات داشته که در اینجا در نظر نگرفته ایم.

Data set استفاده شده

برای ارزیابی رویکرد پیشنهادی و روش های مختلف استفاده شده مانند استخراج خصوصیات ملورها، ساخت بردار ویژگی ملورها و شناسایی و طبقه بندی آنها سایت http://vx.netlux.org/ تعداد زیادی ملور(به صورت کد باینری) دانلود شد و توسط تحلیلگرهای پویای CWSandbox و Anubis در سایتهای http://www.sunbeltsecurity.com/sandbox/default.aspx و http://anubis.iseclab.org تحلیل شده و گزارش رفتار آنها برای استفاده در مراحل بعدی بدست آمد (گزارشات Anubis برای جامعیت بیشتر انتخاب شد) و به data set اضافه شد. البته از بین بیش از ۳۰۰۰۰ گزارش آماده، رفتار ملورها که حاصل تحلیل توسط Anubis هستند در قالب xml نیز به طور تصادفی تعداد زیادی گزارش رفتار ملورها انتخاب شد و به data set ما از گزارشات رفتار ملور ها اضافه شد، این گزارشات آماده در سایت http://pi1.informatik.uni-mannheim.de/malheur قابل دانلود هستند. data set های با نمونه هایی با تعداد ۱۰۰ تا ۱۰۰۰۰ نمونه در آزمایشات مختلف مورد استفاده قرار گرفت و رویکرد پیشنهادی بر روی آنها اعمال شد، که نتایج نهایی طبقه بندی و تشخیص نوع ملور ها در تمام موارد رضایت بخش بود. نتایج data set ی با تعداد ۳۱۳۱ نمونه در این گزارش ارائه شده است. نمونه ها به صورت تصادفی و از لیست متفاوت و متنوعی از ملورها انتخاب شده اند.
فهرست منابع و مراجع

 

[۱].     H. Anton, Elementary Linear Algebra 5e, John Wiley & Son Inc, 1987.

[۲].     I. K. Fodor, “A survey of dimension reduction techniques,” technical report, Lawrence Livemore National Laboratory, June 2002.

[۴].     Yunyue Zhu, High Performance Data Mining in Time Series: Techniques and Case Studies, Ph.D. Dissertation, New York University, January 2004.

[۵].     Lindsay I Smith, A tutorial on Principal Components Analysis, 2002.

[۶].     M. Dash, H. Liu, Feature Selection for Classification. Intelligent Data Analysis 1:131-156, 1997.

[۷].     Schlimmer, J.C., Efficiently inducing determinations: A complete and systematic search algorithm that uses optimal pruning. In: Proceedings of Tenth International Conference on Machine Learning, 284–۲۹۰, (۱۹۹۳).

[۸].     Kira, K. and Rendell, L.A., The feature selection problem: Traditional methods and a new algorithm. In: Proceedings of Ninth National Conference on Artificial Intelligence, 129–۱۳۴, ۱۹۹۲٫

[۹].     Kononenko, I., Estimating attributes: Analysis and extension of RELIEF. In: Proceedings of European Conference on Machine Learning, 171–۱۸۲, ۱۹۹۴٫

[۱۰]. Segen, J., Feature selection and constructive inference. In: Proceedings of Seventh International Conference on Pattern Recognition, 1344–۱۳۴۶, ۱۹۸۴٫

[۱۱]. Xu, L., Yan, P. and Chang, T., Best first strategy for feature selection. In: Proceedings of Ninth International Conference on Pattern Recognition, 706–۷۰۸, ۱۹۸۸٫

[۱۲]. Bobrowski, L., Feature selection based on some homogeneity coefficient. In: Proceedings of Ninth International Conference on Pattern Recognition, 544–۵۴۶, ۱۹۸۸٫
azsoftir.com
09367292276
09367292276
azsoftir@gmail.com
azsoftir.com
09367292276
09367292276
azsoftir@gmail.com
azsoftir.com
[۱۳]. Cardie, C., Using decision trees to improve case-based learning. In: Proceedings of Tenth International Conference on Machine Learning, 25–۳۲, ۱۹۹۳٫

[۱۴]. Koller, D. and Sahami, M., Toward optimal feature selection. In: Proceedings of International Conference on Machine  learning, 1996.

[۱۵]. Quinlan, J.R., C4.5: Programs for Machine Learning. Morgan Kaufmann, San Mateo, California, 1993.

[۱۶]. Sheinvald, J., Dom, B. and Niblack, W., A modelling approach to feature selection. In: Proceedings of Tenth International Conference on Pattern Recognition, 1:535–۵۳۹, June 1990.

[۱۷]. Rissanen, J., Modelling by shortest data description. Automatica, 14:465–۴۷۱, ۱۹۷۸٫

[۱۸]. Mucciardi, A.N. and Gose, E.E., A comparison of seven techniques for choosing subsets of pattern recognition. IEEE Transactions on Computers, C-20:1023–۱۰۳۱, September 1971.

[۱۹]. Modrzejewski, M., Feature selection using rough sets theory. In: Proceedings of the European Conference on Machine Learning (P. B. Brazdil, ed.), 213–۲۲۶, ۱۹۹۳٫

[۲۰]. Oliveira, A.L. and Vincentelli, A.S., Constructive induction using a non-greedy strategy for feature selection. In: Proceedings of Ninth International Conference on Machine Learning, 355–۳۶۰, Morgan Kaufmann, Aberdeen, Scotland, 1992.

[۲۱]. Liu, H. and Setiono, R., A probabilistic approach to feature selection—a filter solution. In: Proceedings of International Conference on Machine Learning, 319–۳۲۷, ۱۹۹۶٫

[۲۲]. Brassard, G., and Bratley, P., Fundamentals of Algorithms. Prentice Hall, New Jersey, 1996.

[۲۳]. Devijver, P.A. and Kittler, J., Pattern Recognition: A Statistical Approach. Prentice Hall, 1982.

[۲۴]. Caruana, R. and Freitag, D., Greedy attribute selection. In: Proceedings of Eleventh International Conference on Machine Learning, Morgan Kaufmann, New Brunswick, New Jersey, 28–۳۶, ۱۹۹۴٫

[۲۵]. Doak, J., An evaluation of feature selection methods and their application to computer security. Technical report, Davis, CA: University of California, Department of Computer Science, 1992.

[۲۶]. Moore, A.W. and Lee, M.S., Efficient algorithms for minimizing cross validation error. In: Proceedings of Eleventh International Conference on Machine Learning, Morgan Kaufmann, New Brunswick, New Jersey, 190–۱۹۸, ۱۹۹۴٫

[۲۷]. Domingos, P., Context-sensitive feature selection for lazy learners. Artificial Intelligence Review, 1996.

[۲۸]. Queiros, C.E. and Gelsema, E.S., On feature selection. In: Proceedings of Seventh International Conference on Pattern Recognition, 1:128–۱۳۰, July-Aug 1984.

[۲۹]. Ichino, M. and Sklansky, J., Feature selection for linear classifier. In: Proceedings of the Seventh International Conference on Pattern Recognition, volume 1, 124–۱۲۷, July–Aug 1984.

[۳۰]. Ichino, M. and Sklansky, J., Optimum feature selection by zero-one programming. IEEE Trans. on Systems, Man and Cybernetics, SMC-14(5):737–۷۴۶, September/October 1984.

[۳۱]. Geoffrion, A.M., Integer programming by implicit enumeration and balas, method. SIAM Review, 9:178–۱۹۰, ۱۹۶۷٫

[۳۲]. Foroutan, I. and Sklansky, J., Feature selection for automatic classification of non-gaussian data. IEEE Transactions on Systems, Man, and Cybernatics, SMC-17(2):187–۱۹۸, ۱۹۸۷٫

[۳۳]. Liu, H. and Setiono, R., Feature selection and classification—a probabilistic wrapper approach. In: Proceedings of Ninth International Conference on Industrial and Engineering Applications of AI and ES, 284–۲۹۲, ۱۹۹۶٫

 

[۱] نرم افزار بداندیش – Malicious Software- Malware usually includes all types of software and computer code that can be damaging or corrupt your computer. Malware includes viruses, adware, spyware, and Trojans.

[۲] Dynamic Analyser

[۳] Feature Selection/ Reduction

[۴] Pattern Recognition

[۵] Virtual Machine

[۶] طبقه بندی

[۷] Representation

[۸] DLL

[۹] load

[۱۰] Data Mining Practical Machine Learning Tools and Techniques 2d ed – Morgan Kaufmann

[۱۱] Classification

[۱۲] Feature Reduction

[۱۳] Classification

[۱۴] Regression

[۱۵] Clustring
[۱۶]